Encontramo-nos numa época longínqua onde há 100 anos dura uma
guerra entre a Nação do Fogo e o Reino da Terra. Soube-se de
fonte segura que o Reino da Terra planeia usar espionagem contra
a Nação do Fogo, pelo que os generais do Fogo decidiram criar um
enigma que apenas eles e o seu povo conseguissem resolver.
Seguindo a sua capacidade algorítmica lendária e de forma a honrar os famosos números do Fogo, criaram o seguinte problema para verificar a identidade de um verdadeiro cidadão da Nação do Fogo:
Dado um intervalo [A..B], quantos números do Fogo existem no mesmo? Sendo um cidadão da Nação do Fogo deves saber que um "número do Fogo" é um número cujos dígitos não formam nem uma sequência decrescente, nem uma sequência crescente. Por exemplo,
Está agora na altura de mostrares que és digno de ser um cidadão da grande Nação do Fogo!
Dado um intervalo [A..B] (A e B incluídos), a tua tarefa calcular a quantidade de números do Fogo que estão contidos no intervalo. Um número do Fogo é um número cujos dígitos não formam nem uma sequência crescente, nem uma sequência decrescente (sem alterar a ordem dos dígitos no número, claro).
Na primeira linha vem um inteiro C que representa o número de casos de teste. Cada uma das C linhas seguintes representa um caso de teste.
Cada caso de teste é composto por apenas uma linha com dois números inteiros A e B, os limites do intervalo a considerar.
O output contém C inteiros representando a quantidade de números do Fogo no intervalo respectivo.
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:
| 1 ≤ T ≤ 1 000 | Número de casos de teste |
|---|---|
| 0 ≤ A ≤ B < 263 | Tamanho do intervalo |
Para um conjunto de casos de teste valendo 35% dos pontos, T=1 e 0 ≤ A ≤ B ≤ 1 000 000.
Para um conjunto de casos de teste valendo 60% dos pontos, T ≤ 10 e 0 ≤ A ≤ B ≤ 1012.
2
7 1230
42 730
700
392