Square sum numbers

★★★★★

0 votes

Details

Submissions

Discussion

Editorial

Problem

Count number of integers $X$ , such that $L\leq X \leq R$ and sum of digits of $X$ is a perfect square.

Input

First line contains $T$ , number of testcases, $T$ testcases follow
First line of each testcase contains two space separated integers $L$ and $R$

Output

For each test print an integer number of integers in range $[L,R]$ , whose sum of digits is a perfect square.
Answer can be large so output it modulo $10^9+7$

Constraints

$1\leq T \leq 10$
$1 \leq L \leq R \leq 10^{100}$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

In first test $L$ is $1$ and $R$ is $10$ , there are $4$ integers in this range with perfect square digit sum $1$ , $4$ , $9$ and $10$ , therefore answer for first test is $4$
In second test there are $3$ integers which satisfy the condition $90, 97$ and $100$