Note that the memory limit is unusual in this problem.

Consider the infinite sequence of positive rational numbers $x_1$, $x_2$, $\ldots$ given by $x_1=1$, and for all integers $i \geq 2$,

For each positive integer $i$, let $y_i$ be the smallest positive integer such that $\dfrac{y_i}{x_i}$ is an integer. We can show that $y_i$ exists and is well-defined for all positive integers $i$.

There are $q$ queries. For each $1 \le j \le q$, the $j$-th query specifies two integers $l_j\le r_j$, and you should output the sum of all the $y$ values with indices from $l_j$ to $r_j$ inclusive, or mathematically, $$\sum^{r_j}_{i=l_j} y_i$$ modulo $998244353$.

Input

The first line contains a single positive integer $q$, denoting the number of queries.

The $j$-th of the next $q$ lines contains two positive integers $l_j,r_j$ each, which describes the $j$-th query.

Output

For each query, output the required sum modulo $998244353$ on a separate line.

Constraints

For all test cases, $1\le q\le 10^5$, $1\le l_j\le r_j\le 10^{18}$ for all $1\le j\le q$.

Subtask 1 (7 points): $l_j=r_j\le 10^5$ for all $1\le j\le q$.

Subtask 2 (9 points): $r_j\le 10^5$ all $1\le j\le q$.

Subtask 3 (8 points): $l_j=r_j$ for all $1\le j\le q$

Subtask 4 (11 points): for each $1 \le j \le q$, there exists some non-negative integer $k_j$ such that $l_j=2^{k_j}$ and $r_j=2^{k_j+1}-1$.

Subtask 5 (18 points): $q=1$.

Subtask 6 (21 points): $q\le 5000$.

Subtask 7 (26 points): No additional constraints..