Augustus Sheauhaw Jang 目前有许多封臣，具体地来讲是 mmm 个封臣。而在帝国内部，有许多派系在暗流涌动，他们意图颠覆 Sheauhaw 的统治！
目标是 aaa 的派系，能取得多少封臣的共识呢？每个封臣有一个编号 xxx, 0≤x<m0\le x< m0≤x<m. 若 gcd(a,m)=gcd(a+x,m)\gcd(a,m)=\gcd(a+x,m)gcd(a,m)=gcd(a+x,m), 那么这个封臣就会取得派系的共识，加入这个派系！
现在 Sheauhaw 想知道，对于已知的派系目标和封臣数量, 会有多少名封臣加入这个派系。
第一行一个正整数 TTT, 表示数据组数。
每组数据输入一行。每组数据输入两个个整数 a,ma,ma,m, 表示需要求解的派系目标和封臣数量.
每组数据输出一行，一行一个整数，表示加入派系的封臣数量。
3 4 9 5 10 42 9999999967
6 1 9999999966
1≤T≤501≤T≤50 1≤T≤50
1≤a<m≤10101≤a<m≤10^{10} 1≤a<m≤1010