Tubby the doggu wants you to solve a problem for him/her.

You have to find number of numbers between L to R inclusive whose binary representation of length P contains equal number of $0's$ and $1's$. It is guaranteed that $P \ge ceil(log_2(R+1))$ . Here $ceil(x)$ denotes the largest integer greater than or equal to x.

Example : Binary representation of number 5 of length 5 is $00101$.

Input Format

The first line will consist of the integer T denoting the number of test cases.

For each of the T test cases, there will be single line containing 3 integers $L,R$ $and$ P.

Output Format

For each of the T test cases, output a single integer denoting the number of numbers between L to R inclusive whose binary representation of length P contains equal number of $0's$ and $1's$.

Constraints

$1 \le T \le 300000$

$1 \le L \le R \le 10^{16}$

$1 \le P \le 60$

$P \ge ceil(log2(R+1))$

WARNING: Large Input/output data, be careful with certain languages.