Dracula

En Tarija, 2014, Dracula a retornado de un largo sueno, ahora, por supuesto todos los ciudadanos de Tarija quieren escapar de la ciudad. La unica manera de escapar de la ciudad es en buses, para subir en ellos necesitas un ticket.
Todos los tickets estan numerados y disponibles en un rango de A a B inclusive (0 ≤ A, B ≤ 10^18). El costo del ticket es la suma de los digitos del numero del ticket en monedas de oro. (Por ejemplo si nuestro ticket tiene el numero de 14, entonces tiene un costo de 5 monedas de oro (1+4)).

Ahora tu tienes X monedas de oro, por lo que quieres saber cuantos tickets puede comprar con tus X monedas de oro. Desde que estas participando en el concurso de la CCBOL-TARIJA 2014 todos esperan que puedas resolver el problema.

Input

La primera linea de entrada tendremos un numero T que representa la cantidad de casos de prueba, por cada caso de prueba hay una linea compuesta de 3 numeros (0 ≤ A,B, X ≤ 10^18).

Output

Por cada caso de prueba imprimir el numero de tickets que puedes comprar con las X monedas de Oro.

Example

Input:
1
2 5 5


Output:
2