Problem: Process the Q queries below.

* You are given two integers A_i and M_i. Determine whether there exists a positive integer K_i not exceeding 2 × 10^{18} such that A_i^{K_i} ≡ K_i (mod M_i), and find one if it exists.

Constraints

* 1 \leq Q \leq 100
* 0 \leq A_i \leq 10^9(1 \leq i \leq Q)
* 1 \leq M_i \leq 10^9(1 \leq i \leq Q)



Examples

Input

4
2 4
3 8
9 6
10 7


Output

4
11
9
2


Input

3
177 168
2028 88772
123456789 987654321


Output

7953
234831584
471523108231963269

Solution (in CPP):

Solution:
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

const int MAX_OUTPUT = 50000;

long long gcd(long long a, long long b)
{
    return b ? gcd(b, a % b) : a;
}

long long pow(long long x, long long y, long long m)
{
    x %= m;
    long long res = 1;
    for (; y; y >>= 1)
    {
        if (y & 1)
            res = res * x % m;
        x = x * x % m;
    }
    return res;
}

int prim[40000];
int PM[40000];

void prework(){
	int N = 40000;
	int m = 0;
	for (int i = 2; i < N;){
		PM[m++] = i;
		for (int j = i; j < N; j += i)
			prim[j] = 1;
		while(i < N && prim[i])
			i++;
	}
}

int You;
int Riko;

struct number
{
    long long x;
    long long phi;
    vector<int> divs;
    vector<int> degs;

    void update()
    {
		//You++;
        x = 1;
        phi = 1;
        for (int i=0; i < divs.size(); i++)
            for (int j=0; j < degs[i]; j++)
            {
				You++;
                x *= divs[i];
                phi *= divs[i] - !j;
            }
    }

    void factorize()
    {
		//Riko++;
        divs.clear();
        degs.clear();

        long long t = x;
        phi = x;

		for (int i = 0; PM[i] * PM[i] <= t; i++){
			Riko++;
			int d = PM[i];
			if (t % d == 0)
            {
                divs.push_back(d);
                degs.push_back(0);
                for (; t % d == 0; t /= d, degs.back()++);
                phi -= phi / d;
            }
		}

        if (t > 1)
        {
            divs.push_back(t);
            degs.push_back(1);
            phi -= phi / t;
        }
    }
};

const int MAKI = 1;

number unite(number &a, number &b)
{
    number res;

    for (int i=0, j=0; i < a.divs.size() || j < b.divs.size(); )
    {
        if (i == a.divs.size() || i < a.divs.size() && j < b.divs.size() && a.divs[i] > b.divs[j])
        {
            res.divs.push_back(b.divs[j]);
            res.degs.push_back(b.degs[j]);
            j++;
            continue;
        }

        if (j == b.divs.size() || j < b.divs.size() && i < a.divs.size() && b.divs[j] > a.divs[i])
        {
            res.divs.push_back(a.divs[i]);
            res.degs.push_back(a.degs[i]);
            i++;
            continue;
        }

        res.divs.push_back(a.divs[i]);
        res.degs.push_back(max(a.degs[i], b.degs[j]));

        if (a.degs[i] > b.degs[j])
            b.degs[j] = 0;
        else
            a.degs[i] = 0;
        i++;
        j++;
    }

    a.update();
    b.update();
    res.update();
    return res;
}

int kotori;

long long XeqR1modM1andXeqR2modM2(long long r1, long long m1, long long r2, long long m2, long long phi2)
{
	kotori++;
    r1 %= m1;
    r2 %= m2;
    return r1 + m1 * ((r2 + m2 - r1 % m2) * pow(m1, phi2 - 1, m2) % m2);
}

int umi;
int chika = 0;

pair<number, vector<long long> > NpowXeqXmodPpowK(int n, int p, int k)
{
	umi++;
    vector<long long> res;
    number x;

    if (n % p == 0)
    {
        x.divs.push_back(p);
        x.degs.push_back(k);
        x.update();
        res.push_back(0);
        return make_pair(x, res);
    }

    long long z = 1;
	/*
    for (x.x = 1; ; x.x++)
    {
		chika++;
        z = z * n % p;
        res.push_back(x.x);

        if (z == 1)
            break;
    }
	*/
	x.x = p;
    x.factorize();
	x.x = x.phi;
    x.factorize();
	for (int i = 1; i <= 10000 && i <= x.x; i++)
		res.push_back(i);

    for (int i=0, m = p; i<k; i++, m *= p)
        for (int j=0; j<res.size(); j++)
            res[j] = XeqR1modM1andXeqR2modM2(pow(n, res[j], m), m, res[j], x.x, x.phi);

    x.divs.push_back(p);
    x.degs.push_back(k);
    x.update();
    return make_pair(x, res);
}

pair<long long, vector<long long> > NpowXeqXmodM(int n, int m)
{
    number mod;
    mod.x = 1;
    mod.phi = 1;
    vector<long long> x;
    x.push_back(1);

    number mm;
    mm.x = m;
    mm.factorize();
	
	int nico;

    for (int k=0; k < mm.divs.size(); k++)
    {
        pair<number, vector<long long> > cur = NpowXeqXmodPpowK(n, mm.divs[k], mm.degs[k]);

        number mod1 = mod;
        number &mod2 = cur.first;

        vector<long long> x1;
        x1.swap(x);
        vector<long long> &x2 = cur.second;

        if (mod2.x > 1<<30)
        {
            swap(mod1, mod2);
            x1.swap(x2);
        }

        long long d = gcd(mod1.x, mod2.x);
        mod = unite(mod1, mod2);
		int cnt = 2;
		
        for (int i=0; i<x1.size(); i++)
            for (int j=0; j<x2.size(); j++)
            {
                if (x1[i] % d != x2[j] % d)
                    continue;
                x.push_back(XeqR1modM1andXeqR2modM2(x1[i], mod1.x, x2[j], mod2.x, mod2.phi));
				cnt--;
				if (cnt == 0)
					goto KKE;
            }
		KKE:
			assert((int)x.size() > -1);
    }

    return make_pair(mod.x, x);
}

int solve()
{
    int n, m;
    cin >> n >> m;

    pair<long long, vector<long long> > x = NpowXeqXmodM(n, m);
    vector<long long> &r = x.second;

    for (int i=0; i<r.size(); i++) {
        while (r[i] < 0) r[i] += x.first;
        if (r[i] == 0)
            r[i] = x.first;
    }

    sort(r.begin(), r.end());

	if (r.size() == 0) puts("-1");
	else {
		long long ans = r[0];
		if (ans <= 2000000000ll * 1000000000ll)
			cout << ans << endl;
		else
			cout << "-1" << endl;
	}

    return 0;
}

int main(){
	umi = 0;
	kotori = 0;
	You = Riko = 0;
	prework();
	int T;
	cin >> T;
	while(T--){
		solve();
	}
	cerr << chika << endl;
	cerr << umi << endl;
	cerr << kotori << endl;
	cerr << You << ' ' << Riko << endl;
	return 0;
}