Teacher Du is a man who wants to compete in the World Finals for $+\infty$ years. Although the rules do not allow it, he can just change them!

However, since the WF and THUSC are so close this year, he came up with an idea and then abandoned it...

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

Since Teacher Du is busy participating in ACM contests with Teacher Chen and Teacher Xi, can you help him write the standard solution?

Input

The input is read from standard input.

Each test case contains multiple test data.

The first line of the input contains a positive integer $T$ ($1\le T\le 100$), representing the number of test cases.

The next $T$ lines each contain two positive integers $L_i, R_i$, representing $L$ and $R$ for the $i$-th test case, where $1\le L_i\le R_i\le 10^{7}$.

Output

The output is written to standard output.

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

Examples

Input 1

3
1 8
12 24
1 1000000

Output 1

16
16
947158782

Note 1

For $L=1, R=8$, the $16$ valid 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

Subtasks