P7451 [THUSC 2017] Teacher Du

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?

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

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

For $L=1, R=8$, the corresponding $16$ choices are: 1. Empty set. 1. $4$. 1. $3,6,8$. 1. $3,4,6,8$. 1. $2,8$. 1. $2,4,8$. 1. $2,3,6$. 1. $2,3,4,6$. 1. $1$. 1. $1,4$. 1. $1,3,6,8$. 1. $1,3,4,6,8$. 1. $1,2,8$. 1. $1,2,4,8$. 1. $1,2,3,6$. 1. $1,2,3,4,6$. | Test Point $\operatorname*{Id}$ | $R_i\le$ | $T\le$ | $\sum R_i-L_i+1\le$ | Special Constraints | | :----------: | :----------: | :----------: | :----------: | :----------: | | 1~2 | $30$ | $10$ | $10^3$ | None. | | 3 | $100$ | $10$ | $10^3$ | Guaranteed that the answer does not exceed $5\times 10^6$. | | 4 | $100$ | $10$ | $10^3$ | None. | | 5~6 | $10^3$ | $10$ | $10^3$ | $R-L\le22$. | | 7~8 | $10^3$ | $10$ | $10^3$ | Guaranteed that the answer does not exceed $2\times 10^6$. | | 9~10 | $10^3$ | $10$ | $5\times10^3$ | None. | | 11~12 | $10^6$ | $10$ | $10^7$ | $R-L\ge999990$. | | 13~14 | $10^6$ | $10$ | $10^7$ | None. | | 15~20 | $10^7$ | $100$ | $(\operatorname*{Id}-14)\times 10^7$ | None. | Translated by ChatGPT 5