#P18082. Sum and Product

Sum and Product

Sum and Product

定义 f(n,k)f(n,k) 为满足下列条件的有序整数对 (a,b)(a,b) 的数量:

0≤a,b<n,k(a+b)≡ab(modn).0\le a,b<n,\qquad k(a+b)\equiv ab\pmod n.

给定 n,mn,m,计算

∑k=0mf(n,k)(mod998244353).\sum_{k=0}^{m} f(n,k)\pmod{998244353}.

输入格式

第一行整数 TT。每组一行,包含两个整数 n,mn,m。

输出格式

每组输出一行一个整数,即答案对 998244353998244353 取模后的值。

数据范围

  • 1≤T≤1041\le T\le10^4;
  • 1≤n≤10141\le n\le10^{14},0≤m<n0\le m<n;
  • 至多 1010 组数据满足 n>108n>10^8。

样例 1

输入:

4
7 2
100 15
202604 11
1145141 919810

输出:

25
2500
3444208
165721266