Problema A - Códigos preguiçosos

O Duarte tem de escolher um novo código numérico, conhecido como PIN, para o seu cartão multibanco. Como ele é muito preguiçoso, tem receio de se esquecer do código, mas arranjou uma estratégia infalível: vai usar apenas dois dígitos diferentes, tornando assim o código mais fácil de memorizar! Assim, como o PIN de um multibanco tem quatro dígitos, algumas escolhas possíveis que usam apenas dois dígitos diferentes seriam 1331, 4488, 9292, 3030 ou 7755.

Tudo parecia perfeito, mas depois ele pôs-se a pensar e viu que, ao permitir apenas dois dígitos diferentes, estaria a limitar muito a quantidade de códigos possíveis de escolher, facilitando a vida a quem quisesse adivinhar o seu PIN secreto. O Duarte queria perceber exatamente quantos códigos diferentes poderia escolher, e percebeu que o melhor seria resolver de uma vez por todas o problema dos códigos numéricos preguiçosos, não apenas para o seu caso, mas para todos os preguiçosos do mundo, que podiam querer uma quantidade diferente de dígitos.

Sabendo que um código pode ser pensado como sendo simplesmente um número, dada uma quantidade K de dígitos e um intervalo [A,B], o Duarte quer saber quantos números diferentes existem entre A e B (inclusive) que usam no máximo K dígitos diferentes. Para ajudar na memorização, ele não está interessado em números com zeros à esquerda: 00123 não seria portanto um número válido (mas 123 seria).

Por exemplo, se considerarmos o intervalo [98,111]:

• (K=1) Existem 2 números que usam apenas um dígito: 99 e 111
• (K=2) Existem 6 números que usam no máximo dois dígitos: 98, 99, 100, 101, 110 e 111
• (K=3) Existem 14 números que usam no máximo três dígitos : 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110 e 111

O Problema

Dados três inteiros A, B e K, calcular a quantidade Q de números entre A e B que usam no máximo K dígitos diferentes.

Input

Na primeira linha vem um inteiro N, indicando o número de casos a considerar.

Seguem-se exatamente N linhas, cada uma com três inteiros A_i B_i K_i indicando o intervalo e a quantidade de dígitos a considerar para o i-ésimo caso.

Output

O output deve conter N linhas, cada uma com Q_i, a solução para o respetivo caso, ou seja, a i-ésima linha deve conter a quantidade de números no intervalo [A_i, B_i] que usam no máximo K_i dígitos diferentes.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Os casos de teste deste problema estão organizados em 5 grupos com restrições adicionais diferentes:

Input do Exemplo 1

3
98 111 1
98 111 2
98 111 3

Output do Exemplo 1

2
6
14

Explicação do Exemplo 1

Este exemplo corresponde ao mencionado no enunciado.

Input do Exemplo 2

5
23 456 1
541 723 4
4562 9123 2
42 42 3
123 202 1

Output do Exemplo 2

11
183
278
1
0

Explicação do Exemplo 2

Existem 11 números no intervalo [23,456] que usam apenas 1 dígito. Existem 183 números no intervalo [541,723] que usam no máximo 4 dígitos. Existem 278 números no intervalo [4562,9213] que usam no máximo 3 dígitos. Existe 1 número no intervalo [42,42] que usa no máximo 3 dígitos (o próprio 42). Não existe nenhum número que só use no máximo 1 dígito no intervalo [123,202].