You are given two integers a and m. Calculate the number of integers x such that 0 ≤ x < m and \gcd(a, m) = \gcd(a + x, m).

Note: \gcd(a, b) is the greatest common divisor of a and b.

Input

The first line contains the single integer T (1 ≤ T ≤ 50) — the number of test cases.

Next T lines contain test cases — one per line. Each line contains two integers a and m (1 ≤ a < m ≤ 10^{10}).

Output

Print T integers — one per test case. For each test case print the number of appropriate x-s.

Example

Input


3
4 9
5 10
42 9999999967


Output


6
1
9999999966

Note

In the first test case appropriate x-s are [0, 1, 3, 4, 6, 7].

In the second test case the only appropriate x is 0.
import java.util.*;
import java.io.*;
public class Main
{
	class pair{
		long a;int cnt;
		pair(long a,int cnt)
		{this.a=a;this.cnt=cnt;}
	}
	
	void subsequence(ArrayList<pair> product,int store[],int index,ArrayList<Long> arr)
	{
		if(index==store.length)
		{
			get(product,store,arr);
			return;
		}
		
		store[index]=0;
		subsequence(product,store,index+1,arr);
		store[index]=1;
		subsequence(product,store,index+1,arr);
	}
	
	void get(ArrayList<pair> product,int store[],ArrayList<Long> arr)
	{
		long ans=1;int cnt=0;
		for(int i=0;i<store.length;i++)
		{
			if(store[i]==1){cnt++;
			ans=ans*arr.get(i);}
		}
		if(cnt>0)
		{product.add(new pair(ans,cnt));}
		
		return;
	}
	
	long gcd(long a,long b){if(a==0)return b;return gcd(b%a,a);}
	
	
	Main() throws Exception
	{   
		long mod=(long)1e9+7;
		FastReader sc=new FastReader();
		int t=sc.nextInt();
		while(t-->0)
		{
			long n,b,temp;
			long a,m;
			a=sc.nextLong();m=sc.nextLong();
			
			long g=gcd(a,m);
			b=m/g;
			a=a/g;
			n=temp=b;
			b--;
			
			ArrayList<Long> arr=new ArrayList<>();
			for(int i=2;i<=Math.sqrt(n);i++)
			{
				int cnt=0;
				while(n%i==0){n/=i;cnt++;}if(cnt>0){arr.add((long)i);}
			}
			if(n!=1){arr.add(n);}
			
			ArrayList<pair> product=new ArrayList<>(); 
			int store[]=new int[arr.size()];
			int index=0;
			subsequence(product,store,index,arr);
			
			long ans=0;
			for(int i=0;i<product.size();i++)
			{
				pair p=product.get(i);
				long occur=b/p.a;
				if(p.cnt%2==1){ans+=occur;}
				else{ans-=occur;}
			}
			
			System.out.println(b-ans);
			
		}
		
	}
	public static void main (String[] args) throws Exception{
		
		new Main();
	}
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
}