题目描述
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
输入格式
见题面
输出格式
见题面
样例输入
100
1 1000000000000000000 1
1 1000000000000000000 3
1 1000000000000000000 5
1 1000000000000000000 7
1 1000000000000000000 9
1 1000000000000000000 11
1 1000000000000000000 13
1 1000000000000000000 15
1 1000000000000000000 17
1 1000000000000000000 19
1 1000000000000000000 21
1 1000000000000000000 23
1 1000000000000000000 25
1 1000000000000000000 27
1 1000000000000000000 29
1 1000000000000000000 31
1 1000000000000000000 33
1 1000000000000000000 35
1 1000000000000000000 37
1 1000000000000000000 39
1 1000000000000000000 41
1 1000000000000000000 43
1 1000000000000000000 45
1 1000000000000000000 47
1 1000000000000000000 49
1 1000000000000000000 51
1 1000000000000000000 53
1 1000000000000000000 55
1 1000000000000000000 57
1 1000000000000000000 59
1 1000000000000000000 61
1 1000000000000000000 63
1 1000000000000000000 65
1 1000000000000000000 67
1 1000000000000000000 69
1 1000000000000000000 71
1 1000000000000000000 73
1 1000000000000000000 75
1 1000000000000000000 77
1 1000000000000000000 79
1 1000000000000000000 81
1 1000000000000000000 83
1 1000000000000000000 85
1 1000000000000000000 87
1 1000000000000000000 89
1 1000000000000000000 91
1 1000000000000000000 93
1 1000000000000000000 95
1 1000000000000000000 97
1 1000000000000000000 99
1 1000000000000000000 101
1 1000000000000000000 103
1 1000000000000000000 105
1 1000000000000000000 107
1 1000000000000000000 109
1 1000000000000000000 111
1 1000000000000000000 113
1 1000000000000000000 115
1 1000000000000000000 117
1 1000000000000000000 119
1 1000000000000000000 121
1 1000000000000000000 123
1 1000000000000000000 125
1 1000000000000000000 127
1 1000000000000000000 129
1 1000000000000000000 131
1 1000000000000000000 133
1 1000000000000000000 135
1 1000000000000000000 137
1 1000000000000000000 139
1 1000000000000000000 141
1 1000000000000000000 143
1 1000000000000000000 145
1 1000000000000000000 147
1 1000000000000000000 149
1 1000000000000000000 151
1 1000000000000000000 153
1 1000000000000000000 155
1 1000000000000000000 157
1 1000000000000000000 159
1 1000000000000000000 161
1 1000000000000000000 163
1 1000000000000000000 165
1 1000000000000000000 167
1 1000000000000000000 169
1 1000000000000000000 171
1 1000000000000000000 173
1 1000000000000000000 175
1 1000000000000000000 177
1 1000000000000000000 179
1 1000000000000000000 181
1 1000000000000000000 183
1 1000000000000000000 185
1 1000000000000000000 187
1 1000000000000000000 189
1 1000000000000000000 191
1 1000000000000000000 193
1 1000000000000000000 195
1 1000000000000000000 197
1 1000000000000000000 199
样例输出
1000000000000001
1000000000000001
1000000000000001
1000000000000001
1000000000000001
1000000000000001
1000000000000001
1000000000000001
1000000000000001
1000000000000001
1000000000000001
1000000000000001
1000000000000001
937529386565633
937529386565633
937529386565633
937529386565633
937529386565633
937529386565633
937529386565633
937529386565633
875062578740223
875062577526901
875062577526901
875062576313579
875062576313579
875062575100257
875062575100257
812646932807681
812646932807681
812646932807681
812646932807681
812646932807681
812646932807681
812646932807681
812646932807681
750238889682065
750238889682065
750238889682065
750238889682065
750238888483505
750180115372721
750176319373313
687764479049729
687764479049729
687764479049729
687764479049729
687764479049728
687705709437597
687705709437598
687705709437598
625297660274896
625297660274896
625297660274896
625297656776243
625297656776243
625293865615361
625293865615360
562940529983488
562940529983489
562940529983489
562940529983489
562940529983489
562940529983489
562940529983489
562881756872705
500532204065133
500473699373420
500473698145336
500473698145337
500469916549121
500411146936990
500411146936990
442279806886558
442221305678140
442221305678140
442162797487775
442162797487774
442162794004480
442162794004481
442162794004481
384034980487817
383976478037064
383976478037064
383972952716617
383972684281161
383972680826880
383972680826881
325899845468161
325899845468161
325899577047040
325899577047040
325899577047040
325841072355328
325841072340992
325841072340992
267771755207960
267771755207961
267768236982273
267768236982273