Квадрат числа 26 равен 676 — палиндрому. Также палиндром получится, если в квадрат возвести 2285. Этими и подобными числами заинтересовался Рамазан, дав им название золотых. Все эти числа он мог бы выписать на полях Демидовича, но там слишком мало места. Каждому, кто сможет внести хоть какой-то вклад в развитие теории золотых чисел (то есть, не палиндромов, дающих палиндромы при возведении в квадрат), Рамазан обещает дать два пирожка: с картошкой и капустой. Не сто тысяч марок, конечно, но тоже достойная награда. Покажите, что вы заслуживаете этот приз.
В первой строке целое число $$$M$$$ от 1 до $$$10^5$$$ — количество запросов. В следующих $$$M$$$ строках по два целых числа $$$L_i$$$, $$$R_i$$$ такие, что $$$1 \leqslant L_i \leqslant R_i \leqslant 10^9$$$.
$$$M$$$ строк, на каждой из которых одно целое число — количество золотых чисел в сегменте $$$[L_i, R_i]$$$.
3 2 3 22 33 222 333
0 1 2
Золотыми числами из третьего запроса являются 264 и 307 ($$$264^2=69696$$$, $$$307^2=94249$$$).