问题 4810 --相同gcd

4810: 相同gcd

时间限制: 1 Sec  内存限制: 128 MB
提交: 24  解决: 11
[提交][状态][命题人:]

题目描述

给你一个a,m，然你计算有多少x满足 gcd(a,m)=gcd(a+x,m) 并且（0≤x＜m）

输入

第一行一个t，代表数据组数，其中（1≤t≤50）

每组数据输入两个整数a和m，其中（1≤a＜m≤1e10）

输出

每组数据输出单独一行的答案
样例输入
Copy
3
4 9
5 10
42 9999999967
样例输出
Copy
6
1
9999999966

提示

来源

 

[提交][状态]