HAP01 - Play with Binary Numbers

no tags 

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. T=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.
Answer of each each test case should be on 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

hide comments
prakash: 2016-12-27 19:28:38

very easy

madhavgaba: 2016-07-05 19:22:13

didn't understand.....same code AC in C but TLE in C++

pulkitgulati: 2016-07-03 21:20:43

such a beautiful implementation of bitwise operator...worth solving

mcjoshi: 2016-02-27 04:27:15

Wooo.....
AC in one go!!!

shantanu tripathi: 2015-08-29 18:55:33

@ admin 15011977 plzz check this id why its giving TLE....and when i changed variable from int to long long it got AC..

chin: 2015-06-18 15:57:03

Brute force works!!!..:D

vank: 2014-09-14 13:07:19

So here comes the Century :)

Barack Obama: 2014-08-21 21:49:36

submission id 12204868, it shows wrong answer.....but test cases running well....what are the possible problems...??

vb30: 2014-06-18 10:40:57

AC...
100th classical!!!

Bhavik: 2014-02-13 09:30:09

brute force works....AC in first attempt


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