Migrated from Lutece 3021 简单数论 2

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

这是一道简单的数论题，至少它的题面很简单。

给出若干组正整数 $p$ 和 $x$，求方程 $a^2+b^2\equiv x\pmod p$ 关于 $a$ 和 $b$ 在模 $p$ 意义下解的组数。其中 $p$ 是奇数且不含平方因子。

Input

第一行包括一个正整数 $t(1\leq t\leq 10^5)$，表示询问组数。

接下来 $t$ 行每行包括两个正整数 $p,x(0\leq x\leq p-1,p\leq 10^7)$。

Output

输出 $t$ 行，第 $i$ 行包括一个正整数，代表第 $i$ 个方程解的组数。

Samples

1
5 0

9

Note

$9$ 组解分别为 $(a,b) = (0,0),(1,2),(1,3),(2,1),(2,4),(3,1),(3,4),(4,2),(4,3)$。

Resources

2023 UESTC ICPC Training for Math