OP Bro loves numbers.He is trying to solve the following problem. Given A , B and K.Find the number of numbers between A and B such that Xor ( i ) * Or ( i ) < = K. For a number i Xor ( i ) is obtained by xoring all the digits of the number and Or ( i ) is obtained by oring all digits. Help OP Bro solve this problem.

Input :

First line contains T<=100. Number of TestCases

Next T lines contain 3 integers A,B,K

1 <= A <= B <= 10^18

1 <= K <= 500

Output :

For each test case, output a single integer denoting the answer of the problem.