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.