---{"category_name":"easy","problem_code":"SDSQUARE","problem_name":"Square Digit Squares","languages_supported":{"0":"ADA","1":"ASM","2":"BASH","3":"BF","4":"C","5":"C99 strict","6":"CAML","7":"CLOJ","8":"CLPS","9":"CPP 4.3.2","10":"CPP 4.9.2","11":"CPP14","12":"CS2","13":"D","14":"ERL","15":"FORT","16":"FS","17":"GO","18":"HASK","19":"ICK","20":"ICON","21":"JAVA","22":"JS","23":"LISP clisp","24":"LISP sbcl","25":"LUA","26":"NEM","27":"NICE","28":"NODEJS","29":"PAS fpc","30":"PAS gpc","31":"PERL","32":"PERL6","33":"PHP","34":"PIKE","35":"PRLG","36":"PYTH","37":"PYTH 3.4","38":"RUBY","39":"SCALA","40":"SCM guile","41":"SCM qobi","42":"ST","43":"TCL","44":"TEXT","45":"WSPC"},"max_timelimit":2,"source_sizelimit":50000,"problem_author":"div_adm","problem_tester":null,"date_added":"4-10-2013","tags":{"0":"div_adm","1":"nov13","2":"simple"},"editorial_url":"http://discuss.codechef.com/problems/SDSQUARE","time":{"view_start_date":1384162200,"submit_start_date":1384162200,"visible_start_date":1384162200,"end_date":1735669800},"layout":"problem"}---<span class="solution-visible-txt">All submissions for this problem are available.</span><h3> Read problems statements in <a target="_blank" href="http://www.codechef.com/download/translated/NOV13/mandarin/SDSQUARE.pdf"> Mandarin Chinese </a> and <a target="_blank" href="http://www.codechef.com/download/translated/NOV13/russian/SDSQUARE.PDF"> Russian</a>.</h3><p>Recently Chef become very much interested in perfect squares. We all know Chef and his weird interests. Anyways Chef will be soon writing his masters thesis on perfect squares revealing what-not-known properties of perfect squares.</p><p>While doing his research, he happened to be confronted with some interesting perfect squares. These prefect squares consists only of digits which are themselves perfect squares. 0, 1, 4 and 9 are such digits. These are called perfect digits.</p><p>As we all know Chef also has habit of asking too many questions, he is asking- given two numbers a and b, how many perfect squares exists between these two numbers inclusive, that contains only perfect digits. </p><p><span style="font-weight: bold;">Input:</span></p><p>First line of input will contains T, number of test cases. Then T lines follows, each containing two positive integers a and b.</p><p><span style="font-weight: bold;"> Constraints:</span></p><p>T <= 500</p><p>1<= a <= b <= 10000000000 </p><p><span style="font-weight: bold;">Output:</span></p><p>For each input, output number of perfect digit squares between given numbers. </p><p><span style="font-weight: bold;">Sample</span></p><p><strong>Input:</strong></p><p>2</p><p>1 10</p><p>100 10000</p><p><span style="font-weight: bold;">Output:</span></p><p>3</p><p>9</p>