HAP01 - Play with Binary Numbers

Let S be the binary representation of an integer. We define two functions a(i) and b(i) such that:

  • a(i) = Number of occurrences of '1' at odd positions of S,
  • b(i) = Number of occurrences of '1' at even positions of S.

For example: for integer 19, S = 10011, so a(19) = 2 and b(19) = 1.

Input

First line contains an integer T, the number of test cases. Then T lines follow. On each line, you will be given three integers M, N, K.

Output

For each test case output a single integer R, where R is the number of integers 'i' between M and N (both inclusive) such that absolute difference of a(i) and b(i) is equal to K. The answer to each each test case should be on a separate line.

Constraints

T <= 50
1 <= M < N <= 10^19
1 <= N - M <= 10^6
0 <= K <= 50

Example

Input:
1
1 10 2

Output:
2

Added by::-)
Date:2013-04-16
Time limit:1.201s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:own

hide comments
2013-04-18 16:06:45 RuPp$
getting WA, Can you suggest why?
SUB ID=9118050

Thanks :-) got AC
Silly mistake :(

Last edit: 2013-04-22 05:03:38
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.