题目描述

给定一个整数 $N$。请判断是否存在一组正整数 $(A, B)$，使得 $3^A + 5^B = N$。如果存在，请给出其中一组解。

输入格式

输入为一行，包含一个整数 $N$。

输出格式

如果不存在满足条件的 $(A, B)$，请输出 -1。

如果存在，请输出 $A$ 和 $B$，用空格分隔。如果有多组解，输出任意一组均可。

样例 1

输入

106

输出

4 2

样例 2

输入

1024

输出

-1

样例 3

输入

10460353208

输出

21 1

说明/提示

限制

• $1 \leq N \leq 10^{18}$
• 输入均为整数。

样例解释 1

因为 $3^4 + 5^2 = 81 + 25 = 106$，所以 $(A, B) = (4, 2)$ 满足条件。

由 ChatGPT 4.1 翻译