Given an integer N, find how many pairs (A,B) are there such that: gcd(A,B) = A xor B where 1 ≤ B ≤ A ≤ N. Here gcd(A,B) means the greatest common divisor of the numbers A and B. And A xor B is the value of the bitwise xor operation on the binary representation of A and B. Input The first line of the input contains an integer T (T ≤ 10000) denoting the number of test cases. The following T lines contain an integer N (1 ≤ N ≤ 30000000). Output For each test case, print the case number first in the format, ‘Case X:’ (here, X is the serial of the input) followed by a space and then the answer for that case. There is no new-line between cases. Explanation Sample 1: For N = 7, there are four valid pairs: (3, 2), (5, 4), (6, 4) and (7, 6). Sample Input 2 7 20000000 Sample Output Case 1: 4 Case 2: 34866117