You are given two array A = (a1, a2, a3 ... an) and B = (b1, b2, b3 ... bn). The productof these element is calculated as a1 * b1 + a2 * b2 + a3 * b3 + ... + an * bn. Now your task is to choose the subsequence of elements of array A and subsequence of elements of array B (same length and non-empty), which product value is Minimum.

Before the operation you are allowed to permute each subsequence as your wish.

Input

The first line of input contains the number T- the number of test cases.

For each test case first line contains the number N.The next two lines contain Nintegers each, giving the values of array A and array Brespectively.

Limits

T <= 20

1 <= N <= 100000

-100000 <= a[i], b[i] <= 100000

Output

For each test case, output a line,

Case X: Y

where Xis the test case number, starting from 1and Yis required answer.

Example

Input:
2
5
-2 -3 -1 3 2
-5 -3 -2 1 2
3
1 3 -5
-2 4 1

Output:
Case 1: -29
Case 2: -26