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.IOException;
import java.util.*;
import java.lang.Math;

public class demo {
	public static void main(String[] args) {
		int t,n,sl=-1;
		long a,b,c;
		long[] arr=new long[100];
		Scanner sc= new Scanner(System.in);
		t=sc.nextInt();
		for (int i=0;i<t;i++)
		{
			sl=-1;
			c=0;
			a=sc.nextLong();
			b=sc.nextLong();
			long k=gcd(a,b);
			long b1=b/k;
			for (int j=1;j<=Math.sqrt(b1);j++)
				if (b1%j==0)
				{
					if (kt(j))
					{
						++sl;
						arr[sl]=j;
					};
					if (b1/j!=j && kt(b1/j))
					{
						++sl;
						arr[sl]=b1/j;
					};
				};
			long b2=b/a+1;
			for (int j=1;j<=sl+1;j++) 
			{
				long z=dequy(j,arr,sl,k,1,b,0,a);
				if (j%2==0) c-=z; else c+=z;
			};
			long so1=(long) a/k;
			long so2=(long) (b+a-1)/k;
			System.out.println(so2-so1+1-c);
		};
	};
	public static long gcd(long a,long b)
	{
		if (b==0) return a; else return gcd(b,a%b); 
	};
	public static boolean kt(long a)
	{
		if (a==1) return false;
		for (int i=2;i<=Math.sqrt(a);i++)
			if (a%i==0) return false;
		return true;
	};
	public static long dequy(int n,long[] arr,int sl,long tich,int k,long b1,int dau,long a)
	{
		long kq=0;
		for (int i=dau;i<=sl;i++)
		{
			tich*=arr[i];
			if (k==n)
			{
				long tam1=(long) Math.floor((double) a/tich)+1;
				long tam2=(long) Math.floor((double) (b1+a)/tich);
				kq+=tam2-tam1+1;
			} else kq+=dequy(n,arr,sl,tich,k+1,b1,i+1,a);
			tich/=arr[i];
		}
		return kq;
	}
}
