I. Colorings Counting

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$.

Sample Input

4
4 2
4 3
6 3
2023 808

Sample Output

1
2
5
304535191

Source

2023“钉耙编程”中国大学生算法设计超级联赛（7）