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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.ArrayList;

public class Main
{
	public static void main(String[] args) {
		new Thread(null, new Runnable() {
			public void run() {
                solve();
            }
        }, "1", 1 << 26).start();
	}
	static void solve () {
		FastReader fr =new FastReader();	PrintWriter op =new PrintWriter(System.out);
 
 		int t =fr.nextInt() ,j ;	long a ,m ,dm ,g ,i ;	ArrayList<Long> prm =new ArrayList<>() ;
 		while (t-- > 0) {
 			a =fr.nextLong() ;	m =fr.nextLong() ;	g =gcd (m,a) ;
 			a/=g ;	m/=g ;	dm =m ;

 			if ((m&1l)==0l) {
 				prm.add(2l) ;	while ((m&1l)==0l)	m>>=1 ;
 			}
 			for (i =3l ; i*i<=m ; i+=2l) {
 				if ((m%i) == 0l) {
 					prm.add(i) ;	while ((m%i) == 0l)	m/=i ;
 				}
 			}
 			if (m>2l)	prm.add(m) ;

 			for (j =0 ; j<prm.size() ; ++j)	dm -= (dm/prm.get(j)) ;
 			op.println(dm) ;	prm.clear() ;
 		}
		op.flush();	op.close();
	}	
	static long gcd (long num , long den) {
		return (num%den == 0l ? den : gcd (den,num%den)) ;
	}
	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();
		}

		String nextLine() {
			String str ="";

			try
			{
				str =br.readLine();
			}
			catch(IOException e)
			{
				e.printStackTrace();
			}

			return str;
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next()) ;
		}
	}
}