Strange Bank

To make it difficult to withdraw money, a certain bank allows its customers to withdraw only one of the following amounts in one operation:

• 1 yen (the currency of Japan)

• 6 yen, 6^2(=36) yen, 6^3(=216) yen, ...

• 9 yen, 9^2(=81) yen, 9^3(=729) yen, ...

At least how many operations are required to withdraw exactly N yen in total?

It is not allowed to re-deposit the money you withdrew.

Constraints

• 1 \leq N \leq 100000
• N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

If at least x operations are required to withdraw exactly N yen in total, print x.

Examples

Input

127

Output

4

Input

3

Output

3

Input

44852

Output

16

inputFormat

Input

Input is given from Standard Input in the following format:

N

outputFormat

Output

If at least x operations are required to withdraw exactly N yen in total, print x.

Examples

Input

127

Output

4

Input

3

Output

3

Input

44852

Output

16

样例

3

3