Given is an integer N.
Determine whether there is a pair of positive integers (A, B) such that 3^A + 5^B = N, and find one such pair if it exists.

-----Constraints-----
 - 1 \leq N \leq 10^{18}
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N

-----Output-----
If there is no pair (A, B) that satisfies the condition, print -1.
If there is such a pair, print A and B of one such pair with space in between. If there are multiple such pairs, any of them will be accepted.

-----Sample Input-----
106

-----Sample Output-----
4 2

We have 3^4 + 5^2 = 81 + 25 = 106, so (A, B) = (4, 2) satisfies the condition.

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
n = int(input())
for i in range(1, 100):
	if 3 ** i > n:
		print(-1)
		break
	x = n - 3 ** i
	for j in range(1, 100):
		if x == 5 ** j:
			print(i, j)
			return


n = int(input())
l_3 = []
l_5 = []
t3 = 1
t5 = 1
for i in range(100):
	t3 *= 3
	t5 *= 5
	l_3.append(t3)
	l_5.append(t5)
ans_3 = -1
ans_5 = -1
for i in l_3:
	for j in l_5:
		if i + j == n:
			ans_3 = i
			ans_5 = j
if ans_3 != -1:
	print(l_3.index(ans_3) + 1, l_5.index(ans_5) + 1)
else:
	print(-1)


def resolve():
	n = int(input())
	for i in range(1, 100):
		for j in range(1, 100):
			if 3 ** i + 5 ** j == n:
				print(i, j)
				return
	print(-1)
resolve()


import sys
x = int(input())
for i in range(50):
	for j in range(30):
		if 3 ** (i + 1) + 5 ** (j + 1) == x:
			print(str(i + 1) + ' ' + str(j + 1))
			return
print(-1)


import math
N = int(input())
Amax = math.ceil(18 / math.log10(3))
Bmax = math.ceil(18 / math.log10(5))
for A in range(1, Amax + 1):
	for B in range(1, Bmax + 1):
		if 3 ** A + 5 ** B == N:
			print(A, B)
			return
print(-1)


import sys

def input():
	return sys.stdin.readline().rstrip()

def main():
	n = int(input())
	for a in range(1, 100):
		for b in range(1, 100):
			if 3 ** a + 5 ** b == n:
				print(a, b)
				return
	else:
		print(-1)

def __starting_point():
	main()
__starting_point()


n = int(input())
a = 1
x = 3
while x < n:
	b = 1
	y = 5
	while x + y <= n:
		if x + y == n:
			print(a, b)
			return
		y *= 5
		b += 1
	x *= 3
	a += 1
else:
	print(-1)


n = int(input())
for a in range(1, 100):
	for b in range(1, 200):
		if 5 ** b + 3 ** a == n:
			print(f'{a} {b}')
			return
print(-1)


n = int(input())
for i in range(1, 100):
	for l in range(1, 50):
		if 3 ** i + 5 ** l == n:
			print(str(i) + ' ' + str(l))
			return
print(-1)


import sys
from math import log, ceil
MOD = 10 ** 9 + 7
INF = float('inf')
N = int(input())
for a in range(1, 41):
	for b in range(1, 31):
		if pow(3, a) + pow(5, b) == N:
			print('{} {}'.format(a, b))
			return
print('{}'.format(-1))


import math
n = int(input())
for i in range(1, 26):
	for j in range(1, 38):
		if 3 ** j + 5 ** i == n:
			print(j, i)
			return
print(-1)


n = int(input())
for a in range(1, 40):
	for b in range(1, 40):
		if 3 ** a + 5 ** b == n:
			print(a, b)
			return
print(-1)


import sys
n = int(input())
for a in range(1, 50):
	for b in range(1, 50):
		if 3 ** a + 5 ** b == n:
			print(f'{a} {b}')
			return
print(-1)


N = int(input())
flag = True
for i in range(1, 1000):
	for j in range(1, 1000):
		if 3 ** i + 5 ** j == N:
			print(i, j)
			flag = False
if flag:
	print(-1)


n = int(input())
a = 0
b = 0
count = 0
while 3 ** a < n and count == 0:
	b = 0
	a += 1
	while 3 ** a + 5 ** b < n:
		b += 1
		if 3 ** a + 5 ** b == n:
			count = 1
if count == 1:
	print(a, b)
else:
	print(-1)


N = int(input())
for a in range(1, 39):
	for b in range(1, 27):
		if 3 ** a + 5 ** b == N:
			print(a, b)
			return
print(-1)


N = int(input())
for i in range(1, 54):
	for j in range(1, 36):
		if 3 ** i + 5 ** j == N:
			print(str(i) + ' ' + str(j))
			return
print(-1)


n = int(input())
for i in range(1, 40):
	for j in range(1, 40):
		if 3 ** i + 5 ** j == n:
			print(i, j)
			return
print(-1)


N = int(input())
for i in range(1, 40):
	for j in range(1, 27):
		if pow(3, i) + pow(5, j) == N:
			print(i, j)
			return
print(-1)


n = int(input())
a = 0
a3 = 1
while a3 < n:
	b = 0
	b5 = n - a3
	while b5 % 5 == 0:
		b5 //= 5
		b += 1
	if b5 == 1 and a != 0 and (b != 0):
		print(a, b)
		break
	else:
		a += 1
		a3 *= 3
else:
	print(-1)


N = int(input())
for i in range(1, 38):
	for j in range(1, 26):
		if 3 ** i + 5 ** j == N:
			print(i, j)
			return
print(-1)


N = int(input())
for i in range(1, 100):
	for j in range(1, 100):
		if 3 ** i + 5 ** j == N:
			print(i, j)
			return
print(-1)


t = int(input())
f = 0
for i in range(1, 50):
	for j in range(1, 50):
		k = pow(3, i) + pow(5, j)
		if k == t:
			print(i, j)
			return
print('-1')


N = int(input())
b = 1
flag = 0
while 5 ** b <= N:
	x = N - 5 ** b
	flag = 0
	a = 1
	while 3 ** a <= x:
		if 3 ** a == x:
			flag = 1
			break
		a += 1
	if flag == 1:
		break
	b += 1
if flag == 0:
	print(-1)
else:
	print(a, b)


import sys
from math import gcd, factorial, ceil, floor, sqrt
from bisect import bisect_left, bisect_right
from copy import deepcopy
from heapq import heapify, heappop, heappush
from itertools import permutations, combinations, product, accumulate
from collections import defaultdict, deque, Counter
from functools import lru_cache
sys.setrecursionlimit(10 ** 8)
ii = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(map(int, input().split()))
N = ii()
for a in range(1, 100):
	for b in range(1, 100):
		if pow(3, a) + pow(5, b) == N:
			print(a, b)
			return
print(-1)


N = int(input())
(A, B) = (0, 0)
for i in range(1, 38):
	for j in range(1, 26):
		if 3 ** i + 5 ** j == N:
			(A, B) = (i, j)
			break
		if A > 0:
			break
if A > 0:
	print(A, B)
else:
	print(-1)


n = int(input())
t = []
m = 1
while 3 ** m <= 10 ** 18:
	t.append(3 ** m)
	m += 1
f = []
m = 1
while 5 ** m <= 10 ** 18:
	f.append(5 ** m)
	m += 1
for (a, i) in enumerate(t):
	for (b, j) in enumerate(f):
		if i + j == n:
			print(a + 1, b + 1)
			return
print(-1)


n = int(input())

def search(n):
	for a in range(1, 100):
		pow3 = 3 ** a
		diff_0 = n - pow3
		if diff_0 < 5:
			return (False, -1, -1)
		is_int = True
		diff = diff_0
		b = 1
		while is_int:
			quo = diff // 5 ** b
			rem = diff % 5 ** b
			if quo == 1 and rem == 0:
				return (True, a, b)
			elif rem == 0:
				b += 1
			else:
				is_int = False
(is_exist, a, b) = search(n)
if is_exist:
	print(a, b)
else:
	print(-1)


n = int(input())
ind3 = [0] + [3 ** i for i in range(1, 38)]
ind5 = [0] + [5 ** i for i in range(1, 38)]
flag = False
for a in range(1, 38):
	for b in range(1, 38):
		if ind3[a] + ind5[b] == n:
			print(a, b)
			flag = True
			break
if not flag:
	print(-1)


n = int(input())
a = 1
finished = False
while 3 ** a < n:
	b = 1
	while 3 ** a + 5 ** b <= n:
		if 3 ** a + 5 ** b == n:
			print(a, b)
			finished = True
			break
		b += 1
	if finished:
		break
	a += 1
if not finished:
	print(-1)


n = int(input())
flag = False
for a in range(1, 40):
	for b in range(1, 40):
		if 3 ** a + 5 ** b == n:
			print(a, b)
			flag = True
			break
	if flag:
		break
else:
	print(-1)


N = int(input())
for a in range(1, 100):
	for b in range(1, 100):
		if 3 ** a + 5 ** b > 10 ** 18:
			break
		if 3 ** a + 5 ** b == N:
			print(a, b)
			return
print(-1)


n = int(input())
for i in range(1, 100):
	for j in range(1, 100):
		if int(pow(3, i)) + int(pow(5, j)) == n:
			print(i, j)
			return
print(-1)


n = int(input())
for a in range(1, 100):
	for b in range(1, 100):
		if pow(3, a) + pow(5, b) == n:
			print('{} {}'.format(a, b))
			return
print(-1)


N = int(input())
A = 1
for a in range(1, 100):
	A *= 3
	B = 1
	for b in range(1, 100):
		B *= 5
		if N == A + B:
			print(a, b)
			break
	else:
		continue
	break
else:
	print(-1)


N = int(input())
(A, B) = (0, 0)
for i in range(1, 41):
	for j in range(1, 31):
		if 3 ** i + 5 ** j == N:
			(A, B) = (i, j)
if A == 0 and B == 0:
	print(-1)
else:
	print(A, B)


n = int(input())
X = 10 ** 18
for i in range(X):
	if 3 ** i > X:
		A = i
		break
for i in range(X):
	if 5 ** i > X:
		B = i
		break
for i in range(1, A):
	for j in range(1, B):
		if 3 ** i + 5 ** j == n:
			print(i, j)
			return
print(-1)


N = int(input())
maxa = 39
maxb = 27
det = False
for a in range(1, 39):
	for b in range(1, 27):
		if 3 ** a + 5 ** b == N:
			(ans1, ans2) = (a, b)
			det = True
if det:
	print('{} {}'.format(ans1, ans2))
else:
	print(-1)


def II():
	return int(input())
n = II()
for a in range(1, 38):
	for b in range(1, 26):
		if 3 ** a + 5 ** b == n:
			print(a, b)
			return
print(-1)


from collections import deque
from heapq import heappop, heappush
from random import randint
import time

def main():
	N = int(input())
	idx2 = 1
	while N - pow(5, idx2) >= 1:
		tmp = N - pow(5, idx2)
		idx = 1
		while tmp - pow(3, idx) >= 0:
			if tmp == pow(3, idx):
				print(idx, idx2)
				return 0
			else:
				idx += 1
		idx2 += 1
	print(-1)

def __starting_point():
	main()
__starting_point()


N = int(input())
ans = ['-1']
for i in range(1, 41):
	for j in range(1, 31):
		n = 3 ** i + 5 ** j
		if n == N:
			ans = [str(i), str(j)]
			break
print(' '.join(ans))


n = int(input())
maxA = 1
maxB = 1
while 3 ** maxA <= n:
	maxA = maxA + 1
while 5 ** maxB <= n:
	maxB = maxB + 1
done = False
for a in range(1, maxA):
	for b in range(1, maxB):
		if 3 ** a + 5 ** b == n:
			print(str(a) + ' ' + str(b))
			done = True
			break
if not done:
	print(-1)


N = int(input())
for b in range(1, 30):
	for a in range(1, 40):
		if 3 ** a + 5 ** b == N:
			print(a, b)
			return
print(-1)


N = int(input())
A = 1
ans = [-1 for i in range(2)]
while 3 ** A <= N:
	B = 1
	while 3 ** A + 5 ** B <= N:
		if 3 ** A + 5 ** B == N:
			ans[0] = A
			ans[1] = B
			break
		B += 1
	A += 1
if ans[0] < 0:
	print(-1)
else:
	print(ans[0], ans[1])


n = int(input())
a = 1
b = 1
for a in range(1, 50):
	for b in range(1, 50):
		if 3 ** a > n:
			break
		if 5 ** b > n:
			break
		if 3 ** a + 5 ** b == n:
			print(a, b)
			return
print(-1)


N = int(input())
for i in range(1, 28):
	for j in range(1, 40):
		ans = 5 ** i + 3 ** j
		if ans == N:
			print(j, i)
			return
print(-1)


import sys
N = int(input())
for i in range(1, 50):
	for j in range(1, 50):
		if 3 ** i + 5 ** j == N:
			print(i, j)
			return
print(-1)


import sys
zz = 1
sys.setrecursionlimit(10 ** 5)
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def fori(n):
	return [fi() for i in range(n)]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def ii():
	return input().rstrip()

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def comp(a, b):
	if a > b:
		return 2
	return 2 if a == b else 0

def gi():
	return [xx for xx in input().split()]

def gtc(tc, ans):
	print('Case #' + str(tc) + ':', ans)

def cil(n, m):
	return n // m + int(n % m > 0)

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def gh():
	sys.stdout.flush()

def isvalid(i, j, n, m):
	return 0 <= i < n and 0 <= j < m

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = 1
uu = t
while t > 0:
	t -= 1
	n = fi()
	for i in range(1, 40):
		for j in range(1, 40):
			if 3 ** i + 5 ** j > n:
				continue
			if 3 ** i + 5 ** j == n:
				print(i, j)
				return
	print(-1)


n = int(input())
for a in range(1, 40):
	for b in range(1, 30):
		if 3 ** a + 5 ** b == n:
			print('{} {}'.format(a, b))
			return
else:
	print(-1)


n = int(input())
for i in range(1, 30):
	for j in range(1, 60):
		if 3 ** j + 5 ** i == n:
			print(j, i)
			return
print(-1)


N = int(input())
for a in range(1, 38):
	for b in range(1, 26):
		if 3 ** a + 5 ** b == N:
			print(a, b)
			return
print(-1)


n = int(input())
for i in range(1, 1000):
	for j in range(1, 1000):
		if 3 ** j + 5 ** i == n:
			print(str(j) + ' ' + str(i))
			return
print('-1')


N = int(input())
a = 1
b = 0
while 5 ** b < N:
	b += 1
if b <= 0:
	print(-1)
	return
while 3 ** a <= N:
	while b > 1 and 3 ** a + 5 ** b > N:
		b -= 1
	if 3 ** a + 5 ** b == N:
		print(str(a) + ' ' + str(b))
		return
	else:
		a += 1
print(-1)