設 $f(n, k)$ 為滿足以下條件的整數對 $(a, b)$ 的數量：

• $0 \le a, b < n$。
• $k(a + b) \equiv ab \pmod n$。

給定兩個整數 $n$ 和 $m$，你需要計算：

$$\sum_{k=0}^{m} f(n, k)$$

由於答案可能很大，請輸出其對 $998\,244\,353$ 取模的結果。

輸入格式

輸入包含多組測試資料。第一行包含一個整數 $T$ ($1 \le T \le 10^4$)，表示測試資料組數。對於每組測試資料：

唯一的一行包含兩個整數 $n$ 和 $m$ ($1 \le n \le 10^{14}, 0 \le m < n$)。

保證最多只有 $10$ 組測試資料滿足 $n$ 大於 $10^8$。

輸出格式

對於每組測試資料，輸出一行，包含一個整數，表示答案對 $998\,244\,353$ 取模的結果。

範例

輸入範例 1

4
7 2
100 15
202604 11
1145141 919810

輸出範例 1

25
2500
3444208
165721266