AT_abc428_d [ABC428D] 183184

For positive integers $ x $ and $ y $ , define $ f(x,y) $ as follows: - Let $ z $ be the string obtained by interpreting $ x,y $ in decimal notation as strings and concatenating them in this order. Let $ f(x,y) $ be the value when $ z $ is interpreted as an integer in decimal notation. For example, $ f(3,14)=314,\ f(100,3)=1003 $ . You are given positive integers $ C $ and $ D $ . Find the number of integers $ x $ that satisfy the following conditions: - $ 1 \leq x \leq D $ - $ f(C, C+x) $ is a perfect square. You are given $ T $ test cases, find the answer for each of them.

The input is given from Standard Input in the following format: > $ T $ $ \textrm{case}_1 $ $ \textrm{case}_2 $ $ \vdots $ $ \textrm{case}_T $ $ \textrm{case}_i $ represents the $ i $ -th test case. Each test case is given in the following format: > $ C $ $ D $

Output $ T $ lines. The $ i $ -th line ( $ 1 \leq i \leq T $ ) should contain the answer to the $ i $ -th test case.

### Sample Explanation 1 For the first test case, there are three values of $ x $ that satisfy the conditions: $ x = 5, 37, 80 $ . - When $ x=5 $ , $ f(C, C+5) = f(4,9) = 49 = 7^2 $ - When $ x=37 $ , $ f(C, C+37) = f(4,41) = 441 = 21^2 $ - When $ x=80 $ , $ f(C, C+80) = f(4,84) = 484 = 22^2 $ For the second test case, there are two values of $ x $ that satisfy the conditions: $ x = 1, 3133 $ . - When $ x=1 $ , $ f(C, C+1) = f(183,184) = 183184 = 428^2 $ - When $ x=3133 $ , $ f(C, C+3133) = f(183,3316) = 1833316 = 1354^2 $ For the third test case, there are zero values of $ x $ that satisfy the conditions. For the fourth test case, there are $ 1421 $ values of $ x $ that satisfy the conditions. ### 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 $ - All input values are integers.