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

public class EducationalRound81D {

	public static void solve() {
		int t =  s.nextInt();
		while(t-->0) {
			long a = s.nextLong();
			long m = s.nextLong();
			long y = gcd(a,m);
			
			m/=y;
			
			out.println(phi(m));
//			HashMap<Long,Integer> first = pf(y);
//			HashMap<Long,Integer> second = pf(m);
//			ArrayList<Long> number = new ArrayList<Long>();
//			for(Long x:second.keySet()) {
//				int val = second.get(x);
//				if(!first.containsKey(x)) {
//					number.add(x);
//				}else {
//					if(val>first.get(x)) {
//						number.add(x);
//					}
//				}
//			}
//			long ans = Recur(number, 0, new LinkedList<Long>(), a+m-1, y);
//			ans = (a+m-1)/y - ans;
//			long tempans = Recur(number, 0, new LinkedList<Long>(), a-1, y);
//			tempans = (a-1)/y - tempans;
//			ans -= tempans;
//			out.println(ans);
		}
	}
	
	public static long phi(long number) {
		long result = number;
		for(long i = 2;i*i <= number; i++) {
			if(number%i==0) {
				while(number%i==0) {
					number/=i;
				}
				result -= result / i;
			}
		}
		if(number > 1) {
			result -= result/number;
		}
		return result;
	}
	
	public static long Recur(ArrayList<Long> number,int pos,LinkedList<Long> selected,long range,long start) {
		int n = number.size();
		if(pos==n) {
			if(selected.size()==0) {
				return 0;
			}
			long curr = 1;
			for(Long i : selected) {
				curr*=i;
			}
			start *= curr;
			if(selected.size()%2==1) {
				return range/start;
			}else {
				return -range/start;
			}
		}
		long ans = 0;
		ans+= Recur(number,pos+1,selected,range,start);
		selected.add(number.get(pos));
		ans+= Recur(number,pos+1,selected,range,start);
		selected.removeLast();
		return ans;
	}
	
	public static HashMap<Long,Integer> pf(long n){
		HashMap<Long,Integer> ans = new HashMap<>();
		for(long i = 2;i*i<=n;i++) {
			int count = 0;
			while(n%i==0) {
				n/=i;
				count++;
			}
			if(count!=0) {
				ans.put(i, count);
			}
		}
		if(n!=1) {
			ans.put(n, 1);
		}
		return ans;
	}
	
	public static long gcd(long a, long b) {
		if (a == 0)
			return b;
		return gcd(b % a, a);
	}

	public static void main(String[] args) {
		out = new PrintWriter(new BufferedOutputStream(System.out));
		s = new FastReader();
		solve();
		out.close();
	}

	public static FastReader s;
	public static PrintWriter out;

	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

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

		double nextDouble() {
			return Double.parseDouble(next());
		}

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

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception e) {
				e.printStackTrace();
			}
			return str;
		}
	}

	
}
