题目描述
快速幂求逆元
给定 n组 ai,pi，其中 pi是质数，求 ai 模 pi的乘法逆元，若逆元不存在则输出 impossible。
注意：请返回在 0∼p−1之间的逆元。

样例
输入：
3
4 3
8 5
6 3
输出：
1
2
impossible

对于某种运算，如果存在一个元素，使得该元素与另一个元素进行这种运算后，结果为该结构的单位元，那么这两个元素就互为逆元。
费马小定理：如果 p 是一个质数，而整数 a 不是 p 的倍数，则有 a^(p-1) ≡ 1 (mod p)。
可变化为a*a^(p-2)=1（mod p）;则a^(p-2)为a的逆元

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");
        }
    }
}