Chef wants to gift pairs to his friends this new year. But his friends like good pairs
only.
A pair (a , b) is called a good pair if 1 <= a < b <= N such that GCD(a*b , P) = 1.
Since Chef is busy in preparation for the party, he wants your help to find all the
good pairs.
—————————————————————————————————————
INPUT
• The first line of the input contains a single integer T.
• The first and only line of each test case contain two integer N,P.
————————————————————————————————————————
OUTPUT
For each test case, print a single line containing one integer — the total number of good
pairs
————————————————————————————————————————
CONSTRAINTS
• 1 ≤ T≤ 50
• 2 ≤ N,P ≤10^5
—————————————————————————————————————
Example Input
2
2 3
3 3
————————————————————————————————————————
Example Output
1
1
# cook your dish here
    
def G(x, y): 
   while(y): 
       x, y = y, x % y 
   return x 
# t=int(input())
# l=list(map(int,input().split()))
for _ in range(int(input())):
    n,p=map(int,input().split())

    c=0
    for i in range(1,n+1):
        if G(i,p)==1:
            c+=1
    ans=c*(c-1)//2
    print(ans)
# cook your dish here
    
def G(x, y): 
   while(y): 
       x, y = y, x % y 
   return x 
# t=int(input())
# l=list(map(int,input().split()))
for _ in range(int(input())):
    n,p=map(int,input().split())

    c=0
    for i in range(1,n+1):
        if G(i,p)==1:
            c+=1
    ans=c*(c-1)//2
    print(ans)