题号：NC214197
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 64 M，其他语言128 M
64bit IO Format: %lld
题目描述
青竹大佬吃香蕉有一个习惯面对一堆的香蕉只吃与幸运数字有关的香蕉，例如现在幸运数字是a，有一堆大小为n的香蕉，将n个香蕉从0到n-1进行编号，青竹大佬只吃第i个香蕉i满足（gcd(a+i，n)=gcd(a,n))。
也就是说
if(gcd(a+i,n)==gcd(a,n)){
青竹就会吃编号为i的香蕉
}
现在请问幸运数字为a有一堆大小为n的香蕉，青竹能吃到多少个香蕉呢？
输入描述:
第一行包含单个整数。T (1≤T≤100)-测试用例的数量。
接下来T行分别是a(幸运数字),n(一堆香蕉的数量)。（1<a<n<10^12 (1后面12个零) )
输出描述:
输出T组数字，青竹大佬能吃到的香蕉数量。