$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