409230: GYM103463 J Hsueh- owns large quantities of apples

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. Hsueh- owns large quantities of applestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

The difference between this problem and LTS owns large quantities of apples is more than the data range, please read the statement carefully.

There are $$$n$$$ apples in Hsueh-'s bag, and $$$m$$$ kids around the man. Let's label these children $$$1$$$ to $$$m$$$.

Hsueh- take all of the apples and gave to the first child.

  • The first child got $$$n$$$ apples from Hsueh-. Next, he ate an apple and the remaining apples could just be divided into $$$x$$$ piles. He took the $$$x - 1$$$ piles and gave the remaining pile to the second child.
  • The second child got $$$\displaystyle \frac{(n - 1)}{x}$$$ apples from the first child. Next, he ate an apple and the remaining apples could just be divided into $$$x$$$ piles. He took the $$$x - 1$$$ piles and gave the remaining pile to the third child.
  • $$$\cdots$$$
  • The $$$i$$$-th child got some apples from the ($$$i - 1$$$)-th child. Next, he ate an apple and the remaining apples could just be divided into $$$x$$$ piles. He took the $$$x - 1$$$ piles and gave the remaining pile to the ($$$i + 1$$$)-th child.
  • $$$\cdots$$$
  • The last child got some apples from the Penultimate child, Next, he ate an apple and the remaining apples could just be divided into $$$x$$$ piles. He took $$$x - 1$$$ piles and go away.

It should be noted that the number of apples in a pile left by last child must be a positive integer.

Until the last child go away, Hsueh- wants to know what is the minimum $$$n$$$ that meets all requirements.

Since $$$n$$$ can be very large, output $$$n$$$ modulo $$$998244353$$$. Formally, let $$$M = 998244353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Input

There are several test cases.

The first line contains a single integer $$$T(1 \leq T \leq 10^3)$$$, denoting the number of test cases. Then follow all the test cases.

For each test case, the first line contains two integers $$$m(1 \leq m \leq 10^9)$$$ and $$$x(2 \leq x \leq 10^9)$$$, denoting the number of children and the number of piles in operation of each child.

Output

For each test case, print a single integer in one line: minimum of $$$n$$$ modulo $$$998244353$$$ that meets all requirements.

ExampleInput
1
1000000000 1000000000
Output
720560972

加入题单

上一题 下一题 算法标签: