Problem Statement

You are given a positive integer $N$ and integers $n,m$ satisfying $0 \leq n \lt m \leq N$.

The function $f$ defined by the following pseudocode computes the greatest common divisor of non-negative integers $i$ and $j$ by the Euclidean algorithm.

function f(i, j)
    if i = 0 then
        return j
    end if

    return f(j mod i, i)
end function

Here, j mod i denotes the remainder when $j$ is divided by $i$. Suppose that $f(i,j)$ is executed once for every pair of integers $(i,j)$ satisfying $0 \leq i\leq j \leq N$. Find the number of times $f(n,m)$ is called, modulo $998244353$.

More formally, find the integer printed by the following pseudocode, modulo $998244353$.

answer ← 0

function f(i, j)
    if (i, j) = (n, m) then
        answer ← answer + 1
    end if

    if i = 0 then
        return j
    end if

    return f(j mod i, i)
end function

for i = 0 to N do
    for j = i to N do
        f(i, j)
    end for
end for

output answer

Solve $T$ test cases for each input.

Constraints

• $1 \leq T \leq 10^5$
• $1 \leq N \leq 10^{18}$
• $0 \leq n \lt m \leq N$
• The sum of $\left\lfloor\frac{N}{m}\right\rfloor$ over all test cases is at most $10^6$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case $\mathrm{case}_t$ is given in the following format:

N n m

Output

Print $T$ lines in total. The $t$-th line should contain the answer for the $t$-th test case.