You are the president of the United Communities of Contest Programming. In order to maintain the reputation of UCCP, you need to solve a simple, yet interesting problem. You are given an array A of N positive integers. You can perform the following operations on the given array some number of times (maybe no operation at all), but not more than once on a particular element of the array:

• Choose an index i of the array. Change A_i to some positive number X > A_i. The cost of this operation is |A_i + X| x |A_i - X|.

You have to perform the operation to make the GCD (Greatest Common Divisor) of all the elements of the array greater than 1. But you have to do it at the minimum total cost. You also need to find the maximum GCD you can make with the minimum total cost. Can you make the GCD great again?

The first line will contain a single integer T. Each test case will have a single integer N, denoting the number of elements of array A. The following line will contain N space separated integers A₁, A₂, ..., A_N denoting the elements of array A.

Constraints

• 1 ≤ T ≤ 20
• 1 ≤ N ≤ 10⁵
• 1 ≤ A_i ≤ 10⁶

For each case, print one line with Case x: y z, where x is the case number, y is the minimum total cost to make the GCD of all the elements of array A greater than 1 and z is the maximum GCD you can make with the minimum total cost.