GCD XOR

Given an integer N, nd 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 rst 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 rst 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

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 using namespace std; 7 int ans[30000010]={
    0}; 8 void init() 9 {10     int i,j;11     for(i=1;i<30000010;i++)12     {13         for(j=i+i;j<30000010;j+=i)14         if((j^(j-i))==i)ans[j]++;15     }16     for(i=1;i<30000010;i++)ans[i]+=ans[i-1];17 }18 int main()19 {20     int t,i,n;21     init();22     scanf("%d",&t);23     for(i=1;i<=t;i++)24     {25         scanf("%d",&n);26         printf("Case %d: %d\n",i,ans[n]);27     }28 }