Let $f(n,k)$ be the number of integer pairs $(a,b)$ such that:
$0 \le a,b < n$.
$k(a+b) \equiv ab \pmod n$.
Given two integers $n$ and $m$, you need to calculate
$$\sum_{k=0}^{m} f(n,k)$$
Since the answer may be large, output it modulo $998\,244\,353$.
Input
There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^4$), indicating the number of test cases. For each test case:
The only line contains two integers $n$ and $m$ ($1 \le n \le 10^{14}$, $0 \le m < n$).
It is guaranteed that there are at most 10 test cases with $n$ greater than $10^8$.
Output
For each test case, output one line containing an integer, indicating the answer modulo $998\,244\,353$.
Examples
Input 1
4 7 2 100 15 202604 11 1145141 919810
Output 1
25 2500 3444208 165721266