import java.io.*;
import java.util.*;
class Solution
{
public int modInverse(int a, int m)
{
for(int i=1; i<m; i++){
if(a*i%m == 1)
return i;
}
return -1;
}
}
class Main {
public static void main (String[] args) {
//taking input using Scanner class
Scanner sc=new Scanner(System.in);
//taking testcases
int T=sc.nextInt();
while(T-->0)
{
Solution obj=new Solution ();
int a,m;
//taking input a and m
a=sc.nextInt();
m=sc.nextInt();
//calling function modInverse()
System.out.println(obj.modInverse(a,m));
}
}
}