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¹⁹
1 ≤ N - M ≤ 10⁶
0 ≤ K ≤ 50

Example

Input:
1
1 10 2

Output:
2