Rikka with Number

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?  

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})$.

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

2
5 20
123456 123456789

3
114480

2017 Multi-University Training Contest - Team 5