AT_arc233_b [ARC233B] Count of Euclid Function Call
Description
正整数 $ N $ と、 $ 0 \leq n \lt m \leq N $ を満たす整数 $ n,m $ が与えられます。
以下の擬似コードで定義される関数 $ f $ は、非負整数 $ i $ と $ j $ の最大公約数をユークリッドの互除法で求める関数です。
```
function f(i, j)
if i = 0 then
return j
end if
return f(j mod i, i)
end function
```
ただし、`j mod i` は $ j $ を $ i $ で割った余りを表します。
$ 0 \leq i\leq j \leq N $ を満たすすべての整数の組 $ (i,j) $ について $ f(i,j) $ を $ 1 $ 回ずつ実行したとき、 $ f(n,m) $ が呼び出される回数を $ 998244353 $ で割った余りを求めてください。
より厳密には、以下の擬似コードが出力する整数を $ 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
```
$ 1 $ つの入力につき、 $ T $ 個のテストケースを解いてください。
Input Format
入力は以下の形式で標準入力から与えられる。
> $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $
各テストケース $ \mathrm{case}_t $ は以下の形式で与えられる。
> $ N $ $ n $ $ m $
Output Format
答えを合計 $ T $ 行で出力せよ。 $ t $ 行目には、 $ t $ 番目のテストケースの答えを出力せよ。
Explanation/Hint
### Sample Explanation 1
$ 1 $ つ目のテストケースでは、 $ (N,n,m)=(5,1,2) $ です。
$ f(2,3) $ を実行したとき、
$ f(2,3) \rightarrow f(1,2) \rightarrow f(0,1) $
の順に呼び出されるため、 $ f(1,2) $ が呼び出される回数は $ 1 $ 回です。
$ (i,j)=(1,2),(2,3),(2,5),(3,5) $ のそれぞれについて $ f(i,j) $ を実行すると $ f(1,2) $ は $ 1 $ 回ずつ呼び出されるため、 $ 1 $ つ目のテストケースの答えは $ 4 $ です。
### Constraints
- $ 1 \leq T \leq 10^5 $
- $ 1 \leq N \leq 10^{18} $
- $ 0 \leq n \lt m \leq N $
- すべてのテストケースにおける $ \left\lfloor\frac{N}{m}\right\rfloor $ の総和は $ 10^6 $ 以下
- 入力される値はすべて整数