Given an integer array of N integers, find the sum of bit differences in all the pairs that can be formed from array elements. Bit difference of a pair (x, y) is the count of different bits at the same positions in binary representations of x and y. For example, bit difference for 2 and 7 is 2. Binary representation of 2 is 010 and 7 is 111 (first and last bits differ in two numbers).

Input

Input begins with a line containing an integer T (1<=T<=100), denoting the number of test cases. Then T test cases follow. Each test case begins with a line containing an integer N (1<=N<=10000), denoting the number of integers in the array, followed by a line containing N space separated 32-bit integers.

Output

For each test case, output a single line in the format Case X: Y, where X denotes the test case number and Y denotes the sum of bit differences in all the pairs that can be formed from array elements modulo 10000007.

Example

Input:
1
4
3 2 1 4

Output:
Case 1: 22