Miki je danas naučio šta su to pravilni brojevi, naime, broj je pravilan, ukoliko je strogo veći od zbira kvadrata njegovih cifara. Tako su npr. brojevi $12$ ($12 > 1^2 + 2^2 = 5$) i $24$ ($24 > 2^2 + 4^2 = 20$) pravilni, dok $1$ ($1 = 1^2 = 1$) i $14$ ($14 < 1^2 + 4^2 = 17$) nisu.

Miki treba da odgovori na $Q$ upita, svaki upit je oblika $L$ $R$, a odgovor na taj upit je broj pravilnih brojeva u intervalu $[L,R]$

Opis ulaza

U prvom redu nalazi se broj $Q$ ($1 \leq Q \leq 10^3$), broj upita na koje Miki treba da odgovori. Sledi $Q$ redova, u $i$-tom se nalaze dva broja odvojena razmakom, $L_{i}$ i $R_{i}$ ($1 \leq L_{i} \leq R_{i} \leq 10^9$), koji predstavljaju $i$-ti upit.

Opis izlaza

Treba ispisati $Q$ redova, u $i$-tom redu treba ispisati odgovor na $i$-ti upit, tj. koliko postoji pravilnih brojeva u intervalu $[L_{i},R_{i}]$.

Primer ulaza

3
1 9
5 11
12 20

Primer izlaza

0
2
3

Objašnjenje primera

• U intervalu $[1,9]$ nema pravilnih brojeva.
• U intervalu $[5,11]$ postoje dva pravilna broja, to su $10$ i $11$.
• U intervalu $[12,20]$ postoje tri pravilna broja, to su $12$, $13$ i $20$.