$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$) берілген.

$n$ мәні $10^8$-ден үлкен болатын тест жиынтықтарының саны $10$-нан аспайтынына кепілдік беріледі.

Шығыс деректері

Әрбір тест жиынтығы үшін бір бүтін саннан тұратын бір жолды — $998\,244\,353$ модулі бойынша жауапты шығарыңыз.

Мысалдар

Кіріс мысалы 1

4
7 2
100 15
202604 11
1145141 919810

Шығыс мысалы 1

25
2500
3444208
165721266