ZOJ Modular Inverse

// Naive

#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(0)

//int main()
//{
//    fast;
//    int test , a , m , i , ans = -1;
//    cin >> test;
//    while(test--)
//    {
//        ans = -1;
//
//        cin >> a >> m;
//
//        for(i=1; i<=1000; i++)
//        {
//            if((a * i-1)%m == 0) // a * x  = 1 (mod m) = a * x - 1 = 0 (mod m)
//            {
//                ans = i;
//                break;
//            }
//        }
//
//        if(ans == -1) cout << "Not Exist" << "\n";
//        else cout << ans << "\n";
//    }
//
//    return 0;
//}


// O(lgM)

// Accepted

int EGCD(int a , int b , int *x , int *y)
{
    if(a == 0)
    {
        *x = 0;
        *y = 1;

        return b;
    }

    int x1 , y1;

    int gcd = EGCD(b%a , a, &x1 , &y1);

    *x = y1 - (b / a) * x1; //  from geeksforgeeks analysis part
    *y = x1; // from geeksforgeeks analysis part

    return gcd;
}

void modInverse(int a , int m)
{
    int x , y;

    int g = EGCD(a , m , &x , &y);

    if(g != 1)
    {
        cout << "Not Exist\n";
        return;
    }

    int res = ((x % m) + m) % m;

    if(!res) res += 1;

    cout << res << "\n";
}

int main()
{
    fast;
    int test , a , m;
    cin >> test;
    while(test--)
    {
        cin >> a >> m;

        modInverse(a , m);
    }

    return 0;
}