Processing math: 21%
编程题
                ### 问题描述

在一个古老的城市中,有一座神秘的石柱。据说,这座石柱是由一位伟大的王者建造的,它蕴含着无尽的力量和智慧。但是,这座石柱的秘密被封印了,只有那些可以解开它秘密的人才能领悟它的智慧。

小蓝是一位勇敢的冒险家,她发现这座石柱隐藏了着两个神秘的数字 am。据她猜测,想要解开石柱的秘密,就要找到一个数字 x,使得 gcd,这样就能解开石柱的秘密了。

然而,小蓝追求的可不只是石柱的秘密,她更想知道的是在 [1, m) 中总共有多少个 x 能够解密。请你编写一个程序,计算出满足条件的 x 的数量。

输入格式

第一行包含一个整数 T1\leq T \leq 20),表示测试用例的数量。

接下来 T 行,每行包含两个整数 am(1\leq a < m \leq 10^{9}),表示石柱上刻着的数字和一个神秘的数字。

输出格式

对于每个测试用例,输出一个整数表示满足条件的 x 的数量。

样例输入

2
5 9
6 10

样例输出

6
4
查看答案
赣ICP备20007335号-2