import java.io.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    public static int qmi(int a, int k, int p){
        long res = 1;
        while(k > 0){
            if((k & 1) != 0) res = res * a % p;
            a = (int)((long) a * a % p);
            k >>= 1;
        }
        return (int)res;
    }
    public static void main(String[] args) throws Exception{
        int n = Integer.valueOf(read.readLine());
        while(n -- > 0){
            String[] ss= read.readLine().split(" ");
            int a = Integer.valueOf(ss[0]);
            int m = Integer.valueOf(ss[1]);
            int qmi = qmi(a, m - 2, m);
            if(a % m != 0) System.out.println(qmi);
            else System.out.println("impossible");
        }
    }
}