Problem Description

Given a ring of $n$ nodes. It's required to color each node with one of the colors in $0 \sim m - 1$, and ensure that adjacent points have different colors.

Consider two colorings are different if and only if two colorings sequences $a, b$ cannot be transformed into each other through several of the following three operations:

- Forall $1 \le i \le n$, $a'[i] \gets a[i \bmod n + 1]$, then $a[i] \gets a'[i]$;
- Forall $1 \le i \le n$, $a'[i] \gets a[n - i + 1]$, then $a[i] \gets a'[i]$;
- Forall $1 \le i \le n$, $a'[i] \gets (a[i] + 1) \bmod m$, then $a[i] \gets a'[i]$.

Calculate the different colorings, modulo $998244353$.

Input

The input consists of multiple test cases. The first line contains a single integer $T$ ($1 \le T \le 100$) - the number of test cases. Description of the test cases follows.

The first line of each test case contains two integer $n, m$ ($4 \le n \le 10 ^ {18}$, $2 \le m \le 10 ^ {18}$).

It's guaranteed that $n, m$ are not multiples of $998244353$.

It's guaranteed that there will be no more than $40$ test cases with $n, m > 20$.

It's guaranteed that there will be no more than $20$ test cases with $n, m > 10 ^ 5$.

It's guaranteed that there will be no more than $5$ test cases with $n, m > 10 ^ {13}$.

Output

For each test case, print a single integer - the different colorings, modulo $998244353$.

4
4 2
4 3
6 3
2023 808

1
2
5
304535191