DRACULA - Dracula

no tags 

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 <= 1018. 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 <= 1018 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

hide comments
mahmud2690: 2016-11-05 16:37:03

nice problem :D

Jacob Plachta: 2013-04-26 22:33:57

Fantastic problem, except for one thing... the input values are <= 10^18, not < 10^18 ! :(

Ehor Nechiporenko: 2012-11-20 12:48:37

And finally I've done this! Yeah!

Last edit: 2013-02-26 09:06:25
Diogo Soares [UFAM]: 2012-08-13 21:25:10

Anyone has a critical test case?

Aman Kumar: 2012-08-09 21:00:25

more sample test cases please..

:D: 2012-02-25 20:51:20

Yup, strange unround numbers like 106 always suggest a missing "^"

Devil D: 2012-02-17 11:44:07

its 10^18 i guess

[Retired] Fendy Kosnatha: 2012-02-15 06:02:38

what is the right for A and B??
0 < A,B < 10^18 or 0 < A,B,X < 1018???


Added by:Paulo Costa
Date:2012-01-16
Time limit:3.139s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IME/USP 2 - Brazilian ICPC Training Camp, Jan-Feb/2012