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

Link:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4454

i am not getting any idea, how to solve this problem. Thanks in Advance :)

http://www.spoj.com/problems/HEAPULM/

how to solve this problem?? I tried a lot but i didn't get any idea how to solve this..

Thanks in Advance :)

Jimmy writes down the decimal representations of all natural numbers between and including m and n, (m ≤ n). How many zeroes will he write down?

Input Input starts with an integer T (≤ 11000), denoting the number of test cases.

Each case contains two unsigned 32-bit integers m and n, (m ≤ n).

Output For each case, print the case number and the number of zeroes written down by Jimmy.

Sample Input Output for Sample Input

5

10 11

100 200

0 500

1234567890 2345678901

0 4294967295

Case 1: 1

Case 2: 22

Case 3: 92

Case 4: 987654304

Case 5: 3825876150

what will be the dp states ? as i used the concept of Digit dp , so my states are dp[my current position][my last number][is the number started][is my current digit equal to my target digit] but i am getting correct output for 1st 3 cases, is there anything i am missing ?

http://codeforces.com/contest/724/problem/C

I have been trying to solve this problem , but i don't have any ideas. can anyone help me ?? Thanks in Advance :)