文理学院程序设计在线练习


互质数

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 1310   Accepted Submission(s): 694
Problem Description

Sg认识到互质数很有用。若两个正整数的最大公约数为1,则它们是互质数。

Input

测试数据有多组,先输入第一个整数表示测试组数T(1<=T<=100),然后是T组测试数据,每组先输入1个整数n(1<=n<=100),接下来的n行中每行有一对整数a,b (0<a,b<10^9)。

Output

对于每组测试数据,输出有多少对互质数。

Sample Input
2
1
10 12
5
3 11
5 11
10 12
11 9
11 13
Sample Output
0
4
Source

10级高级语言期中考试