Rikka with Number

Problem Description

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them: In radix $d$, a number $K=(A_1A_2...A_m)_d(A_i \in [0,d),A_1 \neq 0)$ is good if and only $A_1-A_m$ is a permutation of numbers from $0$ to $d-1$. A number $K$ is good if and only if there exists at least one $d \geq 2$ and $K$ is good under radix $d$. Now, Yuta wants to calculate the number of good numbers in interval $[L,R]$ It is too difficult for Rikka. Can you help her?

Input

The first line contains a number $t(1 \leq t \leq 20)$, the number of the testcases. For each testcase, the first line contains two decimal numbers $L,R(1 \leq L \leq R \leq 10^{5000})$.

Output

For each testcase, print a single line with a single number -- the answer modulo $998244353$.

Sample Input

2
5 20
123456 123456789

Sample Output

3

114480

Source

2017 Multi-University Training Contest - Team 5

https://acm.hdu.edu.cn/showproblem.php?pid=6093