ให้ $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