In Transylvania, 1753, Dracula has returned from his long sleep, now, of course, all the citizens of Transylvania want to escape from the city. The only way out of the island is famous boat Hellman, and Petr is the ticket seller.

All tickets available are numbered from A to B, inclusive, with 0 < A, B ≤ 10¹⁸. The cost of a ticket is the sum of the digits of its numbers in gold coins, so, for an example the ticket 14 costs coins 5 (1+4).

Van Helsing has X gold coins, but he does not know which tickets to buy, or how many tickets he can buy at most. Since you are the mathematician of the city, you were charged with solving this problem.

Input

The input contains an integer T, number of test cases. Each test case contains three integers 0 < A, B, X ≤ 10¹⁸ as described in the statement.

Output

For each test case print one line containing an integer, the number of tickets to Van Helsing can buy at most.

Example

Input:
1
2 5 5

Output:
2