Problem Description

There are m different colors of beads. Define a necklace of length n is a cyclic string that successively connects n beads, taking all rotations and overturnings as equivalent.
For example, [1, 2, 3, 4] is equivalent to [2, 3, 4, 1], [3, 4, 1, 2] and [4, 1, 2, 3] (by ro-tation); and [1, 2, 3, 4] is equivalent to [1, 4, 3, 2], [3, 2, 1, 4], [2, 1, 4, 3] and [4, 3, 2, 1] (by overturning).
Moreover, each time you could transpose the beads of color i to color (i mod m) + 1 for all i at the same time.
After some operations, if a necklace A becomes B, then B is equivalent to A.
Count the number of necklaces modulo 998244353.

Input

The first line of the input contains an integer T , denoting the number of test cases.
In each test case, there are two integers n, m in one line, denoting the length of necklaces, and the number of colors.
1 ≤ T ≤ 20, 3 ≤ n ≤ 10^18, 2 ≤ m ≤ 10^18, 998244353 不整除 n, m

Output

For each test case, output one line contains a single integer, denoting the number of necklaces modulo 998244353.

5
3 2
4 2
8 5
9 5
2333 333

2
4
5079
22017
544780894

Hint

For n = 3, m = 2:
- [1, 1, 1], [2, 2, 2] are equivalent
- [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2, 1], [2, 1, 2], [1, 2, 2] are equivalent