麦当劳和麦当娜

Time Limit: 2500 ms Memory Limit: 65536 KiB

Problem Description

在双胞胎兄妹麦当劳麦当娜的生日会上,他们共收到了N个礼物,生日过后他们决定分配这N个礼物(numv+numw=N)。对于每个礼物他们俩有着各自心中的价值vi和wi,他们要求各自分到的礼物数目|numv-numw|<=1,并且各自所衡量的礼物价值的差值|sumv-sumw|尽可能小,现在他们想知道最小的差值是多少。

Input

 第一行为一个整数表示数据组数T。 接下来T组数组,每组数据第一行为一个整数N。(N<=30) 第二行有N个整数,表示麦当劳所衡量的每个礼物的价值vi。(1<=vi<=10000000) 第三行也有N个整数,表示麦当娜所衡量的每个礼物的价值wi。(1<=wi<=10000000)

Output

 对于每组数据,输出最小的差值。

Sample Input

1
3
1 2 3
4 2 1

Sample Output

1

Hint

 

Source

scf0920