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~.