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

2
5 20
123456 123456789

3
114480