package main

import (
	"bufio"
	"fmt"
	"os"
)

type Factor struct {
	p int64
	e int64
}

func sieve(n int) []int {
	isComp := make([]bool, n+1)
	pr := []int{}
	for i := 2; i*i <= n; i++ {
		if !isComp[i] {
			for j := i * i; j <= n; j += i {
				isComp[j] = true
			}
		}
	}
	for i := 2; i <= n; i++ {
		if !isComp[i] {
			pr = append(pr, i)
		}
	}
	return pr
}

func factorize(x int64, primes []int) []Factor {
	res := []Factor{}
	n := x
	for _, p := range primes {
		pp := int64(p)
		if pp*pp > n {
			break
		}
		if n%pp == 0 {
			cnt := int64(0)
			for n%pp == 0 {
				n /= pp
				cnt++
			}
			res = append(res, Factor{pp, cnt})
		}
	}
	if n > 1 {
		res = append(res, Factor{n, 1})
	}
	return res
}

func phi(n int64, primes []int) int64 {
	res := n
	f := factorize(n, primes)
	for _, fe := range f {
		res = res / fe.p * (fe.p - 1)
	}
	return res
}

func gcd(a, b int64) int64 {
	for b != 0 {
		a, b = b, a%b
	}
	if a < 0 {
		return -a
	}
	return a
}

func powmod(a, e, mod int64) int64 {
	res := int64(1 % mod)
	base := a % mod
	for e > 0 {
		if e&1 == 1 {
			res = (res * base) % mod
		}
		base = (base * base) % mod
		e >>= 1
	}
	return res
}

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var t int
	if _, err := fmt.Fscan(in, &t); err != nil {
		return
	}
	type Pair struct {
		b int64
		n int64
	}
	tests := make([]Pair, t)
	maxVal := int64(2)
	for i := 0; i < t; i++ {
		var b, n int64
		fmt.Fscan(in, &b, &n)
		tests[i] = Pair{b, n}
		if b > maxVal {
			maxVal = b
		}
		if n > maxVal {
			maxVal = n
		}
	}
	primes := sieve(int(maxVal))

	for i := 0; i < t; i++ {
		b := tests[i].b
		n := tests[i].n

		bestK := int64(1<<60)
		bestA := 0

		// Kind 1
		fn := factorize(n, primes)
		k1Possible := true
		var k1 int64 = 0
		for _, fe := range fn {
			p := fe.p
			e := fe.e
			cnt := int64(0)
			tb := b
			for tb%p == 0 {
				tb /= p
				cnt++
			}
			if cnt == 0 {
				k1Possible = false
				break
			}
			need := (e + cnt - 1) / cnt
			if need > k1 {
				k1 = need
			}
		}
		if k1Possible {
			if k1 < bestK {
				bestK = k1
				bestA = 1
			}
		}

		// Kinds 2 and 3 require gcd(b,n)=1
		if gcd(b, n) == 1 {
			// multiplicative order r of b mod n
			ph := phi(n, primes)
			r := ph
			fph := factorize(ph, primes)
			for _, fe := range fph {
				p := fe.p
				for r%p == 0 {
					if powmod(b, r/p, n) == 1%n {
						r /= p
					} else {
						break
					}
				}
			}
			// Kind 2 with k = r
			if r < bestK {
				bestK = r
				bestA = 2
			} else if r == bestK && bestA > 2 {
				bestA = 2
			}
			// Kind 3: minimal k with b^k ≡ -1 (mod n)
			target := (n - 1) % n
			k3 := int64(-1)
			if n == 2 {
				// -1 ≡ 1 mod 2 -> same as order r
				k3 = r
			} else {
				if r%2 == 0 && powmod(b, r/2, n) == target {
					k3 = r / 2
				}
			}
			if k3 != -1 {
				if k3 < bestK {
					bestK = k3
					bestA = 3
				} else if k3 == bestK && bestA > 3 {
					bestA = 3
				}
			}
		}

		if bestA == 0 {
			fmt.Fprintln(out, 0)
		} else {
			fmt.Fprintf(out, "%d %d\n", bestA, bestK)
		}
	}
}