该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小喵喵有两个素数$p,q$，现在小喵喵想问你下面这个方程存在几组整数解。

其中$A,B$是整数，$p,q$是输入的两个素数。

并且，小喵喵对不同的$p$和$q$的组合的解的个数感兴趣，所以他会问你$T$次。

输入格式

第一行一个整数$T$，表示问题的组数。

之后每行两个素数$p,q$，意义如上。

输出格式

每行一个整数，表示这组询问的整数解个数。

输入输出样例

3
2 2
2 3
2 5

4
0
8

样例 1 解释

$4=2^2+0^2=(-2)^2+0^2=0^2+2^2=0^2+(-2)^2$，共$4$种情况

$6$不能拆分成平方和的形式。

$10=1^2+3^2=1^2+(-3)^2=(-1)^2+3^2=(-1)^2+(-3)^2=3^2+1^2=3^2+(-1)^2=(-3)^2+1^2=(-3)^2+(-1)^2$，共$8$种情况。

数据规模与约定

对于$60\%$的数据，$p,q<=10^4$。

对于所有的数据，$T<=5000$，$2<=p,q<=10^9$，且$p,q$为素数。