Description

In a game, DerrickLo needs to complete a task of managing a bunch of buildings. These buildings are placed on position $1$ to $M$. Their heights are $1$ to $M$, too. Initially, the building with height $i$ is placed on position $i$, for each $i$ from $1$ to $M$.

There are also $M$ challenges, the $i$-th challenge contains a height factor $l = i$ and a target length $N$. The score of this challenge is the number of $j$ from $1$ to $N$ such that the building with height $j$ is placed on position $(j \times l)$ after rearranging the positions of the buildings. Note that the target lengths of each challenge are the same, but the height factors are distinct.

To rearrange the buildings, DerrickLo needs to give a shift permutation $v$. Whenever he shifts, he moves the building on position $i$ to position $v(i)$ for each $i$ from $1$ to $M$ simultaneously.

Since DerrickLo is not interested in whether he achieved the maximum score, the shift permutation $v$ is chosen uniformly from all permutations of $\{1, 2, \dots, M\}$. However, he is curious that for each challenge $i$, what is the expected score if he shifts $1, 2, \dots, V$ times separately.

Because the number of challenges and shifts are too big, DerrickLo wants you to calculate the sum of the expected scores modulo $998244353$, that is,

$$\left(\sum_{i=1}^M\sum_{k=1}^VE\left(\sum_{j=1}^N[v_k(j) = i \times j]\right)\right) \bmod 998244353$$

where $v_k(j)$ is the position of building with height $j$ after shifting $k$ times based on the shift permutation $v$.

Input Format

This problem has multiple testcases.

The first line contains an integer $T$, the number of testcases.

The following $T$ lines, each contains three integers $N, M, V$, which discribes a testcase.

Note that the input data may NOT fit into a 32-bit integer.

Output Format

$T$ lines, each represents an answer to a testcase in given order.

1
1 2 1

1

Hint

In the sample, $v$ is either $\{1, 2\}$ or $\{2, 1\}$. You need to calculate:

$$\sum_{i=1}^2E([v(1)=i])$$

When $i = 1$, $E([v(1)=1]) = \frac{1}{2}$. When $i=2$, $E([v(1) = 2]) = \frac{1}{2}$. Thus, the sum is $\frac{1 + 1}{2} = 1$.

---

For all testcases:

• $1 \le T \le 5$.
• $1 \le N \le M \le 10^{12}$.
• $2 \le (M \bmod 998244353)$.
• $1 \le V \le 10^{12}$.

Note that the input data may NOT fit into a 32-bit integer.