#1608 BuyingFlowers

12  1 s   128 MB  

Description

Teddy loves roses and Tracy loves lilies. They wish to plant these flowers in a large garden. 

However, the only florist in town sells these flowers in packets which are represented by int[]s roses and lilies. The i-th packet contains roses[i] roses and lilies[i] lilies. Each packet can be bought only once. 

Teddy and Tracy wish to buy some flowers and arrange them into a rectangular grid. This grid must be arranged such that each cell contains exactly one flower, and any two cells which share an edge must contain different kinds of flowers. Additionally, Teddy and Tracy must use all the flowers they buy. 

Teddy and Tracy love square-shaped grids, so they wish to buy a set of packets such that they can arrange the flowers into the most square-like grid possible. More precisely, they wish to arrange the flowers into an R x C grid, where R and C are positive integers, such that |R-C| (|R-C| denotes the absolute value of R-C) is minimized. Print this minimum absolute value, or -1 if no valid arrangement exists.

Input

The first line of the input gives the number of test cases, T (1 <= T <= 200).

For each test case, the first line contains a positive integer p, representing the number of elements in roses and lilies, no more than 16.

The second line contains p integers representing int[] roses where each element will be between 0 and 10000, inclusive.

The third line contains p integers representing int[] lilies where each element will be between 0 and 10000, inclusive.

The total number of flowers in each packet represented by roses and lilies will be greater than 0.

Output

For each test case, print the answer as an integer, in one line.

Sample Input

Sample Output

4
2
2 4
4 2
3
2 7 3
3 4 1
4
4 5 2 1
6 10 5 9
10
1 208 19 0 3 234 1 106 99 17
58 30 3 5 0 997 9 615 77 5
1
0
-1
36