AT_abc428_d [ABC428D] 183184

正整数 $ x,y $ に対して $ f(x,y) $ を以下で定義します。 - 十進表記の $ x,y $ をそれぞれ文字列として解釈しこの順に連結して得られる文字列を $ z $ とする。 $ z $ を十進表記の整数として解釈したときの値を $ f(x,y) $ とする。 たとえば $ f(3,14)=314,\ f(100,3)=1003 $ です。 正の整数 $ C, D $ が与えられます。以下を満たす整数 $ x $ の個数を求めてください。 - $ 1 \leq x \leq D $ - $ f(C, C+x) $ は平方数である $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \textrm{case}_1 $ $ \textrm{case}_2 $ $ \vdots $ $ \textrm{case}_T $ $ \textrm{case}_i $ は $ i $ 番目のテストケースを表す。各テストケースは以下の形式で与えられる。 > $ C $ $ D $

$ T $ 行出力せよ。 $ i $ 行目 ( $ 1 \leq i \leq T $ ) には $ i $ 番目のテストケースに対する答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースにおいて、条件を満たす $ x $ は $ x = 5, 37, 80 $ の $ 3 $ 通りです。 - $ x=5 $ のとき $ f(C, C+5) = f(4,9) = 49 = 7^2 $ - $ x=37 $ のとき $ f(C, C+37) = f(4,41) = 441 = 21^2 $ - $ x=80 $ のとき $ f(C, C+80) = f(4,84) = 484 = 22^2 $ $ 2 $ 番目のテストケースにおいて、条件を満たす $ x $ は $ x = 1, 3133 $ の $ 2 $ 通りです。 - $ x=1 $ のとき $ f(C, C+1) = f(183,184) = 183184 = 428^2 $ - $ x=3133 $ のとき $ f(C, C+3133) = f(183,3316) = 1833316 = 1354^2 $ $ 3 $ 番目のテストケースにおいて、条件を満たす $ x $ は $ 0 $ 通りです。 $ 4 $ 番目のテストケースにおいて、条件を満たす $ x $ は $ 1421 $ 通りです。 ### Constraints - $ 1 \leq T \leq 3 \times 10^5 $ - $ 1 \leq C \leq 2 \times 10^8 $ - $ 1 \leq D \leq 5 \times 10^9 $ - 入力される値はすべて整数