Problema B - Números Divertidos

A professora O.N.I. (Olga Nunes Ildefonso), como tu já sabes, gosta muito de todo o tipo de números. E precisa novamente da tua ajuda!

Recente, reparou que alguns números exibiam uma propriedade interessante: existe um k (inteiro positivo) tal que quando se soma as k-potências dos dígitos do número, obtém-se novamente o número original! Por exemplo, 153 = 1³ + 5³ + 3³. De uma forma mais formal:

D1D2...DN = D1k + D2k + ... + DNk (com k>0)

Aos números que exibem esta propriedade, a professora O.N.I. resolveu chamar de números divertidos. Um outro exemplo de um número divertido é o 4150, já que 4150 = 4⁵ + 1⁵ + 5⁵ + 0⁵.

Consegues ajudar a professor a descobrir estes números?

O Problema

Escreve um programa que determina quantos números divertidos existem num determinado intervalo.

Input

Na primeira linha de input vem um número inteiro C, indicando o número de casos a considerar (1 ≤ C ≤ 10).

Seguem-se exactamente C linhas, cada uma contendo apenas dois números inteiros INF e SUP, separados por um espaço, indicando respectivamente o limite inferior e superior do intervalo a considerar (1 ≤ INF ≤ SUP < 2³¹).

Output

O output é constituído por C linhas, uma para cada caso de input. Cada uma dessas linhas deve conter um único número, indicando quantos números divertidos existem no intervalo [INF,SUP], ou seja, maiores ou iguais a INF e menores ou iguais a SUP.

Exemplo de Input

3
153 153
150 152
5 400

Exemplo de Output

1
0
8