Description

Teacher Du is a man who wants to compete in the World Final for $+∞$ years. Although the rules do not allow it, they can be changed!

But this year, WF is very close in time to THUSC, so he came up with an idea and then just left it alone...

Given $L, R$, among the $R-L+1$ numbers from $L$ to $R$, find how many different subsets can be chosen such that the product of all numbers in the subset is a perfect square. In particular, the empty set is also considered a valid choice, and its product is defined as $1$.

Teacher Du is busy competing in ACM contests together with Teacher Chen and Teacher \cang\ , so can you help Teacher Du write the standard solution?

Input Format

Read input from standard input.

Each test point contains multiple groups of testdata.

The first line contains a positive integer $T$ ($1\le T\le 100$), which is the number of testdata groups.

The next $T$ lines: the $(i+1)$-th line contains two positive integers $L_i, R_i$, representing $L, R$ of the $i$-th group of testdata, and it is guaranteed that $\le L_i\le R_i\le10^7$.

Output Format

Write output to standard output.

Output $T$ lines, each containing one non-negative integer, representing the total number of subsets that satisfy the condition. Output the answer modulo $998244353$.

3
1 8
12 24
1 1000000

16
16
947158782

6
3761870 4957871
2262774 4279409
3027437 5896884
3884310 5021632
3373244 5464739
5063504 5368121

953622420
551347610
583188135
582472626
190680894
268824018

Hint

For $L=1, R=8$, the corresponding $16$ choices are:

1. Empty set.
2. $4$.
3. $3,6,8$.
4. $3,4,6,8$.
5. $2,8$.
6. $2,4,8$.
7. $2,3,6$.
8. $2,3,4,6$.
9. $1$.
10. $1,4$.
11. $1,3,6,8$.
12. $1,3,4,6,8$.
13. $1,2,8$.
14. $1,2,4,8$.
15. $1,2,3,6$.
16. $1,2,3,4,6$.

Translated by ChatGPT 5