Misalkan $f(n, k)$ adalah banyaknya pasangan bilangan bulat $(a, b)$ sedemikian sehingga:

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

Diberikan dua bilangan bulat $n$ dan $m$, Anda perlu menghitung

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

Karena jawabannya bisa sangat besar, keluarkan hasilnya modulo $998\,244\,353$.

Masukan

Terdapat beberapa kasus uji. Baris pertama dari masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^4$), yang menyatakan banyaknya kasus uji. Untuk setiap kasus uji:

Satu-satunya baris berisi dua bilangan bulat $n$ dan $m$ ($1 \le n \le 10^{14}, 0 \le m < n$).

Dijamin bahwa terdapat paling banyak $10$ kasus uji dengan $n$ lebih besar dari $10^8$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi sebuah bilangan bulat, yang menyatakan jawaban modulo $998\,244\,353$.

Contoh

Contoh Masukan 1

4
7 2
100 15
202604 11
1145141 919810

Contoh Keluaran 1

25
2500
3444208
165721266