You are given two integers $x$ and $y$. You want to choose two strictly positive (greater than zero) integers $a$ and $b$, and then apply the following operation to $x$ exactly $a$ times: replace $x$ with $b \cdot x$.

You want to find two positive integers $a$ and $b$ such that $x$ becomes equal to $y$ after this process. If there are multiple possible pairs, you can choose any of them. If there is no such pair, report it.

For example:

if $x = 3$ and $y = 75$, you may choose $a = 2$ and $b = 5$, so that $x$ becomes equal to $3 \cdot 5 \cdot 5 = 75$;

if $x = 100$ and $y = 100$, you may choose $a = 3$ and $b = 1$, so that $x$ becomes equal to $100 \cdot 1 \cdot 1 \cdot 1 = 100$;

if $x = 42$ and $y = 13$, there is no answer since you cannot decrease $x$ with the given operations.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of one line containing two integers $x$ and $y$ ($1 \le x, y \le 100$).


-----Output-----

If it is possible to choose a pair of positive integers $a$ and $b$ so that $x$ becomes $y$ after the aforementioned process, print these two integers. The integers you print should be not less than $1$ and not greater than $10^9$ (it can be shown that if the answer exists, there is a pair of integers $a$ and $b$ meeting these constraints). If there are multiple such pairs, print any of them.

If it is impossible to choose a pair of integers $a$ and $b$ so that $x$ becomes $y$, print the integer $0$ twice.


-----Examples-----

Input
3
3 75
100 100
42 13
Output
2 5
3 1
0 0


-----Note-----

None

Source: codeforces | Difficulty: EASY
Tags: Mathematics

Constructive algorithms


Solutions:
import sys
input = iter(sys.stdin.read().splitlines()).__next__
sys.setrecursionlimit(10000)

def solve(x, y):
	if y % x != 0:
		return (0, 0)
	return (1, y // x)
TC = int(input())
for tc in range(TC):
	(x, y) = map(int, input().split())
	(a, b) = solve(x, y)
	print('%d %d' % (a, b))


import sys, math

def get_intl():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_int():
	return int(sys.stdin.readline().strip())

def get_strl():
	return sys.stdin.readline().strip().split()

def get_str():
	return sys.stdin.readline().strip()

def prt(msg=''):
	if isinstance(msg, list):
		sys.stdout.write(' '.join(map(str, msg)) + '\n')
	else:
		sys.stdout.write(str(msg) + '\n')

def prtY():
	sys.stdout.write('YES\n')

def prtN():
	sys.stdout.write('NO\n')

def prtYN(cond):
	if cond:
		prtY()
	else:
		prtN()
sys.setrecursionlimit(100000000)
MOD = 998244353

def solve():
	(x, y) = get_intl()
	if x > y:
		prt('0 0')
	else:
		remin = y / x
		if y % x == 0:
			print('1 ' + ' ' + str(int(remin)))
		else:
			prt('0 0')

def main():
	haveTestCases = 1
	testCase = 1
	if haveTestCases:
		testCase = get_int()
	for i in range(testCase):
		solve()
main()


t = int(input())
out = ''
for _ in range(t):
	(x, y) = [int(x) for x in input().split()]
	if y % x != 0:
		out += '0 0\n'
	else:
		out += '1 ' + str(y // x) + '\n'
print(out)


list(map(lambda x: print(*[(0, 0), (1, x[1] // x[0])][x[1] % x[0] == 0]), map(lambda s: list(map(int, s.split())), [*open(0)][1:])))


import math as m
i = input()
inp = []
for a in range(0, int(i)):
	inp += [input()]

def nt(x, y):
	if y % x == 0:
		return '1 ' + str(y // x)
	else:
		return '0 0'
for s in inp:
	arr = [int(x) for x in s.split()]
	print(nt(arr[0], arr[1]))


import sys
input = sys.stdin.readline

def solve():
	(x, y) = map(int, input().split())
	if x > y:
		print('0 0')
		return
	if y % x == 0:
		print(f'1 {y // x}')
	else:
		print('0 0')
T = int(input())
for _ in range(T):
	solve()


import sys
input = sys.stdin.readline

def solve():
	(x, y) = map(int, input().split())
	if y % x == 0:
		c = int(y / x)
		return '1 ' + str(c)
	return '0 0'
for _ in range(int(input())):
	print(solve())


import sys
msg = sys.stdin.readlines()
for i in msg[1:]:
	(a, b) = i.split()
	x = int(a)
	y = int(b)
	if y / x == y // x:
		print(1, y // x)
	else:
		print(0, 0)


t = int(input())
l = []
for i in range(t):
	l.append(input())
for i in l:
	(x, y) = [int(j) for j in i.split()]
	if x * y <= 0:
		print('0 0')
	elif y % x == 0:
		print(f'1 {y // x}')
	else:
		print('0 0')


for n in [*open(0)][1:]:
	(x, y) = map(int, n.split())
	print(f'1 {y // x}' if y % x == 0 else '0 0')


t = int(input())
ans = list()
for i in range(0, t):
	(x, y) = [int(p) for p in input().split()]
	if y % x == 0:
		ans.append(f'1 {y // x}')
	else:
		ans.append('0 0')
for s in ans:
	print(s)


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	(x, y) = map(int, sys.stdin.readline().split())
	if y % x == 0:
		print('1', y // x)
	else:
		print('0 0')


import sys
input = lambda : sys.stdin.readline().strip()
for i in range(int(input())):
	(x, y) = map(int, input().split())
	print(1, y // x) if y / x == y // x else print(0, 0)


for s in [*open(0)][1:]:
	(x, y) = map(int, s.split())
	print(*((1, y // x), (0, 0))[y % x > 0])


for t in [*open(0)][1:]:
	(c, v) = map(int, t.split())
	print(*((1, v // c), (0, 0))[v % c > 0])


for n in [*open(0)][1:]:
	(p, r) = map(int, n.split())
	print(*((1, r // p), (0, 0))[r % p > 0])


for a in [*open(0)][1:]:
	(b, c) = map(int, a.split())
	print(*((1, c // b), (0, 0))[c % b > 0])


t = int(input())
arrow = []
while t > 0:
	w = input()
	w = w.split()
	x = int(w[0])
	y = int(w[1])
	if x <= y and y % x == 0:
		ans = '1' + ' ' + str(y // x)
	else:
		ans = '0 0'
	arrow.append(ans)
	t -= 1
for i in range(len(arrow)):
	print(arrow[i])


import sys

def solve():
	(x, y) = map(int, sys.stdin.readline().split())
	if x == y:
		print(1, 1)
		return
	if y % x != 0:
		print(0, 0)
	else:
		print(1, y // x)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


def solve_one():
	(x, y) = map(int, input().split(' '))
	if y % x != 0:
		return (0, 0)
	req_pow = y // x
	return (1, req_pow)

def solve_task():
	t = int(input())
	anss = []
	for _ in range(t):
		anss.append(solve_one())
	for (x, y) in anss:
		print(str(x) + ' ' + str(y))
solve_task()


n = int(input())
a = []
for i in range(n):
	b = tuple(map(int, input().split(' ')))
	c = b[1] // b[0]
	if c * b[0] == b[1]:
		a.append(c)
	elif c == 0:
		a.append(c)
	else:
		a.append(0)
for item in a:
	if item == 0:
		print('0 0')
	else:
		print('1 ' + str(item))


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_ls():
	return list(map(int, sys.stdin.readline().strip().split()))

def main():
	for _ in range(int(input())):
		(x, y) = get_ints()
		if y % x == 0:
			print(1, '', y // x)
		else:
			print('0 0')
main()


a = int(input())
f = []
h = []
g = 2
for q in range(a):
	(s, d) = list(map(int, input().split()))
	if d % s == 0:
		d //= s
		f.append(1)
		h.append(d)
	else:
		f.append(0)
		h.append(0)
for i in range(a):
	print(f[i], h[i])


from sys import stdin, stdout
from collections import defaultdict
input = stdin.readline
from random import randint
import math
import sys
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if y % x == 0:
		print(1, y // x)
	else:
		print(0, 0)


from ast import Return
import sys

def solve():
	(x, y) = map(int, sys.stdin.readline().split())
	if x == y:
		print(1, 1)
		return
	if y % x:
		print(0, 0)
		return
	print(1, y // x)

def main():
	t = int(input())
	while t > 0:
		t -= 1
		solve()
main()


count = int(input())
x = []
y = []
for i in range(0, count):
	p = input().split()
	x.append(p[0])
	y.append(p[1])
for j in range(0, count):
	if int(y[j]) % int(x[j]) == 0:
		print('1 ', int(int(y[j]) / int(x[j])))
	else:
		print('0 0')


for t in [*open(0)][1:]:
	(a, b) = map(int, t.split())
	print(*((1, b // a), (0, 0))[b % a > 0])


a = []
b = []
t = int(input())
for i in range(0, t):
	(x, y) = map(int, input().split())
	if y % x == 0:
		a.append(1)
		b.append(y // x)
	else:
		a.append(0)
		b.append(0)
for i in range(0, t):
	print(a[i], b[i])


t = int(input())
l = []
for _ in range(t):
	l += [list(map(int, input().split()))]
for i in range(t):
	(x, y) = l[i]
	if y / x == y // x:
		print('1', y // x)
	else:
		print('0 0')


import sys

def fn(x, y):
	factor = y / x
	if int(factor) != factor:
		return (0, 0)
	n = 1
	if x == y:
		return (1, 1)
	while factor ** (1 / n) >= 2:
		relevant = factor ** (1 / n)
		if relevant == int(relevant):
			return (n, int(relevant))
	return (0, 0)
input = sys.stdin.readlines()
for i in range(int(input[0].strip('\n'))):
	new_list = [int(x) for x in input[i + 1].strip('\n').split(' ')]
	out = fn(new_list[0], new_list[1])
	print(out[0], out[1])


for i in range(int(input())):
	(x, y) = map(int, input().split())
	if x == 0 or y == 0:
		print('0 0')
	elif y % x == 0:
		print(f'{1} {y // x}')
	else:
		print('0 0')


T = int(input())
while T > 0:
	(x, y) = list(map(int, input().split()))
	if y % x == 0:
		print(f'1 {y // x}')
	else:
		print('0 0')
	T -= 1


test_case = int(input())
while test_case:
	test_case -= 1
	arr = list(map(int, input().split(' ')))
	x = arr[0]
	y = arr[1]
	flag = False
	if x > y:
		print('0 0')
		continue
	if x == y:
		print('1 1')
		continue
	if y % x == 0:
		val = int(y / x)
		print(f'1 {val}')
	else:
		print('0 0')


from math import log
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if y / x != y // x:
		print('0 0')
		continue
	print(1, y // x)


def main():
	N = int(input())
	for _ in range(N):
		(x, y) = [int(x) for x in input().split(' ')]
		if y % x != 0:
			print(f'0 0')
		else:
			print(f'1 {y // x}')
main()


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	if y % x == 0:
		print('1', y // x)
	else:
		print('0 0')


import math
t = int(input())
dic = {'1': 1, '2': 4, '3': 9, '4': 6}
for v in range(t):
	inp = list(map(int, input().split()))
	x = inp[0]
	y = inp[1]
	if x > y or y % x != 0:
		print('0 0')
	else:
		b_raise_to_power_a = y // x
		print(f'1 {b_raise_to_power_a}')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if m % n == 0:
		print(1, m // n)
	else:
		print(0, 0)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if y % x == 0:
		print('1 ' + str(y // x))
	else:
		print('0 0')


t = int(input())
n = 1
while n <= t:
	n += 1
	(x, y) = map(int, input().split())
	if y % x != 0:
		print('0', '0')
	elif y % x == 0 and y // x < 10 ** 9:
		print('1', y // x)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if b % a == 0:
		print('1 ' + str(b // a))
	else:
		print('0 0')


t = int(input())
while t > 0:
	t -= 1
	line = input().split(' ')
	x = int(line[0])
	y = int(line[1])
	if y % x == 0:
		print(f'1 {int(y / x)}')
	else:
		print('0 0')


num_pairs = int(input())
for _ in range(num_pairs):
	(x, y) = map(int, input().split())
	if y % x != 0:
		print('0 0')
		continue
	if x == y:
		print('1 1')
		continue
	print(f'1 {y // x}')


n = int(input())
for i in range(n):
	(x, y) = [int(k) for k in input().split()]
	if y % x != 0:
		print('0 0')
	else:
		print(f'1 {int(y / x)}')


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if y % x:
		print(0, 0)
	elif x == y:
		print(1, 1)
	elif x == 1:
		print(1, y)
	elif y % x == 0:
		print(1, y // x)


t = int(input())
while t > 0:
	t = t - 1
	(x, y) = input().split(' ')
	if int(x) > int(y) or int(y) % int(x) != 0:
		print('0 0')
	elif x == y:
		print('1 1')
	else:
		print(1, int(int(y) / int(x)))


multi = dict()
for i in range(1, 101):
	for j in range(1, 101):
		if i ** j <= 100:
			multi[i ** j] = f'{j} {i}'
n = int(input())
for _ in range(n):
	(x, y) = map(int, input().split())
	if x == y:
		print('1 1')
	elif multi.get(y / x) is not None:
		print(multi[y / x])
	else:
		print('0 0')


t = int(input())
while t > 0:
	(x, y) = map(int, input().split())
	if y % x == 0:
		b = y // x
		a = 1
		print(a, b)
	else:
		print('0 0')
	t -= 1


t = int(input())
while t > 0:
	t -= 1
	flag = 0
	(x, y) = input().split()
	x = int(x)
	y = int(y)
	if y % x != 0:
		print('0 0')
	else:
		print('1', y // x)


t = int(input())
while t:
	(x, y) = map(int, input().split(' '))
	if x > y:
		print('0 0')
	elif x == y:
		print('1 1')
	elif x < y:
		if y % x != 0:
			print('0 0')
		else:
			print('1 ' + str(y // x))
	t = t - 1


def main():
	t = int(input())
	for k in range(t):
		(x, y) = list(map(int, input().split(' ')))
		if y % x != 0:
			print('0 0')
		else:
			print(f'1 {y // x}')
main()


t = int(input())
for i in range(0, t):
	xy = input().split()
	x = int(xy[0])
	y = int(xy[1])
	if y < x:
		print('0 0')
	elif y == x:
		print('1 1')
	elif y % x == 0:
		print(f'1 {y // x}')
	else:
		print('0 0')


m = int(input())
for i in range(m):
	(x, y) = map(int, input().split())
	if x == y:
		print('1 1 ')
	elif x > y:
		print('0 0')
	elif y / x == y // x:
		print('1', y // x)
	else:
		print('0 0')


import math
t = int(input())
for i in range(t):
	n = [int(p) for p in input().split()]
	x = n[0]
	y = n[1]
	d = y / x
	if d == y // x:
		print('1 ' + str(int(d)))
	else:
		print('0 0')


t = int(input())
for i in range(t):
	m = input().split()
	if int(m[1]) % int(m[0]) == 0:
		print(1, int(m[1]) // int(m[0]))
	else:
		print(0, 0)


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	if y % x != 0:
		print('0 0')
	else:
		print('1', end=' ')
		b = y // x
		print(f'{b}')


testcases = int(input())
for i in range(testcases):
	(x, y) = map(int, input().split())
	if y % x != 0:
		print(0, end=' ')
		print(0)
	else:
		z = y // x
		print(1, end=' ')
		print(z)


t = int(input())
for k in range(t):
	(x, y) = list(map(int, input().split()))
	num = y % x
	if num == 0:
		b = y // x
		a = 1
		print(a, b)
	else:
		print(0, 0)


N = int(input())
for _ in range(N):
	(x, y) = [int(i) for i in input().split(' ')]
	if y % x != 0:
		print('0 0')
		continue
	k = y // x
	print(1, k)


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	if b % a == 0:
		print(1, b // a)
	else:
		print(0, 0)


n = int(input())
for i in range(n):
	lst = input().split()
	x = int(lst[0])
	y = int(lst[1])
	if y % x != 0:
		print('0 0')
	else:
		print(1, y // x)


t = int(input())
for _ in range(0, t):
	(x, y) = list(map(int, input().split()))
	d = []
	if x > y:
		print('0 0')
	elif x == y:
		print('1 1')
	elif y % x == 0:
		d.append(1)
		d.append(y // x)
		print(*d, sep=' ')
	else:
		print('0 0')


for l in range(int(input())):
	(x, y) = map(int, input().split())
	n = y % x
	if n != 0:
		print(0, 0)
	else:
		print(1, y // x)


def numTransform(x, y):
	if y % x != 0:
		print(0, 0)
	else:
		print(1, y // x)
for t in range(int(input())):
	(x, y) = [int(i) for i in input().split()]
	numTransform(x, y)


a = int(input())
while True:
	if a == 0:
		break
	(x, y) = map(int, input().split())
	if y % x:
		print('0 0')
	else:
		print(f'1 {y // x}')
	a -= 1