1 /*

 2 题意：

 3 给你一个n*m的矩形，在1到m行，和1到n列上都有一棵树，问你站在（0，0）位置能看到多少棵树

 4

 5 题解：

 6 用（x，y）表示某棵树的位置，那么只要x与y互质，那么这棵树就能被看到。不互质的话说明前面已经有树挡住了这棵树

 7 */

 8 #include<stdio.h>

 9 #include<string.h>

10 #include<iostream>

11 #include<algorithm>

12 #include<math.h>

13 #include<queue>

14 using namespace std;

15 typedef long long ll;

16 ll v[10000],index,n;

17 void oula(ll n)  //获取n的所有质因数

18 {

19     for(ll i=2; i<=sqrt(n); ++i)

20     {

21         if(n%i==0)

22         {

23             v[index++]=i;

24             n/=i;

25             while(n%i==0)

26                 n/=i;

27         }

28     }

29     if(n>1)

30         v[index++]=n;

31 }

32 ll get_result(ll m)//返回1——m这个范围内与n有公因数的数的个数

33 {

34     ll que[10000],i,j,k,t=0,sum=0;

35     que[t++]=-1;

36     for(i=0; i<index; i++)

37     {

38         k=t;

39         for(j=0; j<k; j++)

40             que[t++]=que[j]*v[i]*(-1);

41     }

42     for(i=1; i<t; i++)

43         sum=sum+m/que[i];

44     return sum;

45 }

46 int main()

47 {

48     ll t;

49     scanf("%lld",&t);

50     while(t--)

51     {

52         ll n,m,ans=0;

53         scanf("%lld%lld",&n,&m);

54         ans=0;

55         for(ll i=1;i<=n;++i)

56         {

57             index=0;

58             oula(i);

59             ans+=(m-get_result(m));     //注意这里可不是这样写：ans+=get_result(m);

60         }

61         printf("%lld\n",ans);

62     }

63     return 0;

64 }