BITDIFF - Bit Difference

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

Added by:imranziad
Date:2015-11-24
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:AIUB CS Fest 2015 (H.M. Mehrab)

hide comments
2015-12-05 00:04:53 Filip Sollar
Can I have better than O(n ^ 2) solution ? You have to find all the pairs.. still getting TLE
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.