help-op-bro
Source: hackerearth
Difficulty: MEDIUM

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.

SAMPLE INPUT
1
1 5 25

SAMPLE OUTPUT
5

Explanation

Xor ( 1 )*Or ( 1 ) =1

Xor ( 2 )*Or ( 2 ) =4

Xor ( 3 )*Or ( 3 ) =9

Xor ( 4 )*Or ( 4 ) =16

Xor ( 5 )*Or ( 5 ) =25