问题描述

求二次同余方程 $x ^ 2 + y ^ 2 \equiv r\pmod p$ 满足 $x, y \in [0, p)$ 的解的组数，保证 $\mu(p)$ 不等于 $0$ 且 $p$ 为奇数。多组数据。

输入格式

第一行一个整数 $T$ 表示数据组数。

接下来 $T$ 行，每行两个非负整数 $p, r$。

输出格式

共 $T$ 行，每行一个非负整数表示对应询问的答案。

样例输入输出

样例 1 输入

1
5 0

样例 1 输出

9

数据规模与约定

本题共有 20 个测试点，每个测试点 5 分，限制取遍 $p \leq 10 ^ i (3 \leq i \leq 7)$，$p$ 是否为素数以及 $T \in \{10 ^ 3, 2\times 10 ^ 5\}$ 的所有可能。

对于所有数据，$0 \leq r < p\leq 10 ^ 7$，$\mu(p)$ 不等于 $0$ 且 $2\nmid p$。