GCD

题目描述

给定整数$a$和$m$,计算整数$x$的数量,满足 $0\le x< m$同时$gcd(a,m)= gcd(a+x,m)$

输入格式

第一行一个数字 $T$。

接下来$T$行 $2$ 个整数 $a,m$。

输出格式

T行，每行一个数，表示答案。

样例输入

3
4 9
5 10
42 9999999967

样例输出

6
1
9999999966

数据范围

所有数据保证 $1\le T\le 50,1\le a< m\le 1e10$。