Raccoon Forest Pollution

The forest of Raccoon Ridge can be modeled as an $n \times m$ grid. Industrial wastewater has polluted the Dream Maple Creek, a straight line that traverses the forest, making the regions it crosses harmful for raccoons. In order to study the effects of this pollution, little raccoon CleverRaccoon needs your help.

Define $$f(n,m) = n + m - \gcd(n,m)$$ as the maximum number of grid cells a straight line can pass through in an $n \times m$ grid.

CleverRaccoon has two types of queries for you:

1. Given $n$ and $m$, compute $$f(n,m) = n + m - \gcd(n,m).$$
2. Given $n$, $m$, and $Q$ (with the guarantee that $$f(n,m) < Q$$), find integers $n'\ge n$ and $m'\ge m$ such that $$f(n',m') \ge Q$$ and the area $n'\times m'$ is minimized. Output the value of $n' m' - n m$ modulo $998244353$.

inputFormat

The input begins with a single integer op which indicates the type of query:

• If op = 1, the next line contains two space-separated integers n and m.
• If op = 2, the next line contains three space-separated integers n, m, and Q.

outputFormat

If op = 1, output a single integer representing $$f(n,m) = n + m - \gcd(n,m).$$

If op = 2, output a single integer equal to $$ (n'\times m' - n\times m) \bmod 998244353,$$ where $n'$ and $m'$ are the minimal dimensions satisfying the conditions.

sample

1
3 6

6