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: interview

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():
#====input code===
    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))
# print(Amax,Bmax)

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)

# coding:UTF-8
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())
#a,b = map(int, input().split())
#al = list(map(int,input().split()))
#l = [list(map(int,input().split())) for i in range(n)]
#s=[list(map(int,input().split())) for i in range(n)]
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))


#解説を見て間違っていることに気がついた
#0は含まない！
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 a in range(1, 40):
	for b in range(1, 40):
		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,100):
    for j in range(1,100):
        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,40):
        #print(i,j)
        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)

n = int(input())

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

#import math
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)

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

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())

for i in range(1,100):
  for j in range(1,100):
    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, 40):
    if 3 ** i + 5 ** j == n:
      print(i, j)
      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())

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,38):
    for j in range(1,26):
        if 3**i+5**j==n:
            print(i,j)
            return
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)

# A
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())
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 = 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())
# 3^A <= N = 10^18
# 5^B <= N = 10^18
for i in range(1,100):
    for j in range(1,100):
        if 3**i + 5**j == n:
            print(i,j);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()
#3**37 < 10**18 < 3**38 : 1<=a<=37
#5**25 < 10**18 < 5**26 : 1<=b<=25
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())
#find A and B such that 3^A + 5^B = N
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)

#ARC106 A

N = int(input())

#5 は**25でオーバー
#3 は**38でオーバー


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)

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())
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,40):
    for j in range(1,40):
        #print(i,j)
        if 3**i+5**j==n:
            print(i,j)
            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())
#find A and B such that 3^A + 5^B = N
maxA = 1
maxB = 1
test = 3
while (test <= n):
    maxA = maxA + 1
    test *= 3
test = 5
while (test <= n):
    maxB = maxB + 1
    test *= 5
done = False

testA = 3
for a in range(1, maxA):
    testB = 5
    for b in range(1, maxB):
        if (testA+testB == n):
            print((str(a)+' '+str(b)))
            done = True
            break
        testB *= 5
    testA *= 3
if not done:
    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))


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)