Given a interval [a,b] , calculate the occurrence number of digit k.

First line contains a integer T which is the number of test cases.(T<=1010)
And there are T lines later,which contains three intergers a,b,k.(1<=a<=b<10^9 , 0<=k<=9)

For each test case, you should output the answers and every line only contains one integer.

2
1 10 1
1 11 1

2
4