Problem Description

Given two numbers $x, y$, find how many different sequences $(a_1, a_2, \cdots, a_n)$ of length $n$ have the greatest common divisor of all elements equal to $x$ and the least common multiple equal to $y$.

Two sequences $(a_1, a_2, \cdots, a_n)$ and $(b_1, b_2, \cdots, b_n)$ are considered different if there exists at least one position $i$ such that $a_i \neq b_i$.

Since the answer may be very large, output the result modulo $998\ 244\ 353$.

Input Format

The first line contains an integer $Q$, the number of queries.

The next $Q$ lines each contain three integers $x, y, n$, representing one query. Adjacent integers are separated by a single space. For each query, it is guaranteed that there exists at least one sequence satisfying the conditions.

Output Format

Output $Q$ lines. Each line contains one integer, the answer for each query in order.

3
3 6 2
12 144 3
233 251640 10

2
72
905954656

Hint

For $40\%$ of the test cases, $n \le 30$.
For $70\%$ of the test cases, $n \le 5000$.
For all test cases, $1 \le Q \le 100$, $2 \le n \le 10^5$, $1 \le x, y \le 10^9$.

Translated by ChatGPT 5