n = int(input())
ans = n
for i in range(1,100) :
    for j in range(1,100) :
        if i**j <= n :
            ans = min(ans, n - i**j)
print(ans)