Problem:
 Score : 1400 points    Problem Statement 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)       Inputs Input is given from Standard Input in the following format:  Q  A_1  M_1 : A_Q  M_Q       Outputs In the i -th line, print -1 if there is no integer K_i that satisfies the condition.
Otherwise, print an integer K_i not exceeding 2 × 10^{18} such that A_i^{K_i} ≡ K_i  (mod  M_i) . If there are multiple solutions, any of them will be accepted.       Sample Input 1 4
2 4
3 8
9 6
10 7      Sample Output 1 4
11
9
2  It can be seen that the condition is satisfied: 2^4 = 16 ≡ 4  (mod  4) , 3^{11} = 177147 ≡ 11  (mod  8) , 9^9 = 387420489 ≡ 9  (mod  6) and 10^2 = 100 ≡ 2  (mod  7) .       Sample Input 2 3
177 168
2028 88772
123456789 987654321      Sample Output 2 7953
234831584
471523108231963269

Solution (Python):
from math import gcd
def euler_phi(n):
    res=n
    for x in range(2,int(n**.5)+2):
        if n%x==0:
            res=(res//x)*(x-1)
            while n%x==0:
                n//=x
    if n!=1:
        res=(res//n)*(n-1)
    return res

def biggcd(n,m):
    g=gcd(n,m);res=g;count=2
    while gcd(g**count,m)>res:
        res=gcd(g**count,m)
        count+=1
    return res

def solve(a,m,n):
    if gcd(a,m)==1:
        if m==1: return 1
        phi=euler_phi(m);G=gcd(phi,m);r0=solve(a,G,n);mod=m*phi//G
        return ((((pow(a,n*r0,mod)-n*r0)%mod)//G)*pow(n*phi//G,phi-1,m)*phi+r0)%mod
    big=biggcd(a,m);k0=solve(a,m//big,n*big)
    return big*k0

for i in range(int(input())):
    A,M=map(int,input().split())
    print(solve(A,M,1))

Solution (Python):
from math import gcd

def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

prime=get_sieve_of_eratosthenes_new(32000)

def euler_phi(n):
    res=n
    for x in prime:
        if n%x==0:
            res=(res//x)*(x-1)
            while n%x==0:
                n//=x
    if n!=1:
        res=(res//n)*(n-1)
    return res


def biggcd(n,m):
    g=gcd(n,m)
    res=g
    count=2
    while True:
        test=gcd(g**count,m)
        if test>res:
            res=test
            count+=1
        else:
            break
    return res


def solve(a,m,n):
    
    if gcd(a,m)==1:
        if m==1:
            return 1
        phi=euler_phi(m)
        G=gcd(phi,m)
        r0=solve(a,G,n)
        mod=m*phi//G
        return ((((pow(a,n*r0,mod)-n*r0)%mod)//G)*pow(n*phi//G,phi-1,m)*phi+r0)%mod
    else:
        big=biggcd(a,m)
        k0=solve(a,m//big,n*big)
        return big*k0

for i in range(int(input())):
    A,M=map(int,input().split())
    print(solve(A,M,1))

Solution (Python):
def extgcd(a, b):
  if b == 0:
    return 1
  else:
    x, y, u, v, k, l = 1, 0, 0, 1, a, b
    while l != 0:
      x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
      k, l = l, k % l
    return x
def inved(x, m):
  return x % m
def gcd(x, y):
  while y != 0:
    x, y = y, x % y
  return x
def doubling(n, m, mod):
  y = 1
  base = n
  while m != 0:
    if m % 2 == 1:
      y *= base
      y %= mod
    base *= base
    base %= mod
    m //= 2
  return y
def factorization(n):
  if n == 1:
    return {1: 1}
  else:
    D = {}
    base = n
    p = 2
    while n != 1:
      i = 0
      while n % p == 0:
        i += 1
        n //= p
      if i != 0:
        D[p] = i
      p += 1
      if p * p > base and n != 1:
        D[n] = 1
        break
    return D
def Torshent(n):
  dic = factorization(n)
  S = n
  for i in dic:
    S //= i
    S *= i - 1
  return S
def bin_digits(n):
  cnt = 0
  while n != 0:
    cnt += 1
    n //= 2
  return cnt
def Resque(a, mod):
  if mod == 1:
    return 1
  M = Torshent(mod)
  MM = gcd(M, mod)
  R = Resque(a, MM)
  k = doubling(a, R, mod)
  m, modmod = M // MM, mod // MM
  Tm = Torshent(modmod)
  invm = doubling(m, Tm-1, modmod)
  t = ((k - R) // MM) * invm
  R += t * M
  R %= (mod * M // MM)
  R += (mod * M // MM)
  return R



Q = int(input())
for i in range(Q):
  A, M = map(int, input().split())
  if M == 1:
    print(1)
  else:
    R = Resque(A, M)
    print(R)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
from fractions import gcd
from functools import lru_cache

Q = int(input())
AM = (tuple(int(x) for x in row.split()) for row in sys.stdin.readlines())

U = int(10**4.5 + 100)
euler_phi = np.arange(U,dtype=np.int64)
euler_phi[::2] //= 2
for p in range(3,U,2):
    if euler_phi[p] == p:
        euler_phi[p::p] -= euler_phi[p::p]//p
primes = np.where(euler_phi == np.arange(U)-1)[0]

@lru_cache(None)
def phi(n):
    if n < U:
        return int(euler_phi[n])
    factor = primes[n%primes==0]
    x = n
    for p in factor:
        x -= x//p
        while n%p == 0:
            n //= p
    if n > 1:
        
        x -= x//n
    return int(x)

def F(A,M):
    if M == 1:
        return 1
    
    P = phi(M)
    D = gcd(M,P)
    y = F(A,D)
    """
    A^y = y mod Dを満たしている。x = y + Pt として、A^x = x mod Mを作りたい。
    A^{y+Pt} = A^y mod M となるので、y+Pt = A^y mod M となるようにしたい
    """
    k = pow(A,y,M)
    p,m = P//D,M//D
    
    
    p_inv = pow(p,phi(m)-1,m)
    t = (k-y)//D * p_inv
    y += P*t
    y %= (M*P//D)
    y += (M*P//D)
    return y

for A,M in AM:
    x = F(A,M)
    print(x)

Solution (Python):
def egcd(a, b):
    aa = 1; ab = 0
    ba = 0; bb = 1
    while b:
        q = a // b
        r = a % b
        ra = aa - ba * q
        rb = ab - bb * q
        a, b = b, r
        aa, ab = ba, bb
        ba, bb = ra, rb
    return a, aa, ab


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b): return a // gcd(a, b) * b


def phi(n):
    r = 1
    i = 1
    while n > 1:
        i += 1
        if i*i > n: i = n
        x = 1
        while n % i == 0: n //= i; r *= i - x; x = 0
    return r


def inftowermod(n, m):
    if m == 1: return 0
    if n == 1: return 1
    phim = phi(m)
    return pow(n, inftowermod(n, phim) + phim, m)


def solve_congruence(a1, m1, a2, m2):
    if m2 % m1 == 0: return a2
    if m1 % m2 == 0: return a1
    g, p, q = egcd(m1, m2)
    lm = m1 // g * m2
    w1 = m2 // g * q % lm
    w2 = m1 // g * p % lm
    return ((a1 // g * w1 + a2 // g * w2) * g + a1 % g) % lm


def solve(a, m):
    if a == 0: return m
    phim = phi(m)
    kphim = inftowermod(a, phim)
    km = pow(a, phim + kphim, m)


    ans = solve_congruence(km, m, kphim, phim)
    if ans < phim: ans += lcm(m, phim)
    return ans


for __ in range(int(raw_input())):
    print solve(*map(int, raw_input().split()))