编程题：密码

爱丽丝发现了一个宝箱，但是打开宝箱需要破解若干组密码。
每组密码都是一对数字(p,q)，同时宝箱会给出两个数字A,B作为提示，爱丽丝需要找到所有满足以下条件的(p,q)。
p,q均为质数。
A×p+B×q 是p×q的倍数。
由于满足条件的解有很多，你只需要算出有多少对满足条件的(p,q)。

### 输入格式:

第一行输入1个整数T(1≤T≤1000)表示询问个数。
接下来T行，每行输入两个整数A,B(1≤A,B≤10$$^{12}
$$)表示一个询问。

### 输出格式:

对于每个询问输出一行一个整数，表示答案。

### 输入样例:

in
3
2 3
3 7
10 8


### 输出样例:

out
2
3
3







答案：若无答案欢迎评论