CF333A.Secrets

Gerald has been selling state secrets at leisure. All the secrets cost the same: n marks. The state which secrets Gerald is selling, has no paper money, only coins. But there are coins of all positive integer denominations that are powers of three: 1 mark, 3 marks, 9 marks, 27 marks and so on. There are no coins of other denominations. Of course, Gerald likes it when he gets money without the change. And all buyers respect him and try to give the desired sum without change, if possible. But this does not always happen.

One day an unlucky buyer came. He did not have the desired sum without change. Then he took out all his coins and tried to give Gerald a larger than necessary sum with as few coins as possible. What is the maximum number of coins he could get?

The formal explanation of the previous paragraph: we consider all the possible combinations of coins for which the buyer can not give Gerald the sum of n marks without change. For each such combination calculate the minimum number of coins that can bring the buyer at least n marks. Among all combinations choose the maximum of the minimum number of coins. This is the number we want.

杰拉尔德一直在悠闲地兜售国家机密。所有机密的售价相同：均为 $n$ 马克。杰拉尔德所出售机密的这个国家没有纸币，只有硬币。但该国硬币面额仅限于所有形如 $3$ 的正整数次幂的值：$1$ 马克、$3$ 马克、$9$ 马克、$27$ 马克，依此类推；不存在其他面额的硬币。显然，杰拉尔德喜欢收到恰好为 $n$ 马克的付款（即无需找零）。所有买家也都尊重他，并尽可能在不找零的前提下支付恰好 $n$ 马克。但这种情况并非总能实现。

某天，一位不幸的买家来了。他无法凑出恰好 $n$ 马克而不需找零。于是他掏出自己全部的硬币，试图向杰拉尔德支付一个大于等于 $n$ 马克的金额，并且使用的硬币数量尽可能少。那么，他最多可能收到多少枚找零硬币？

对上一段的严格数学描述如下：我们考虑所有那些无法用若干枚硬币恰好凑出 $n$ 马克的硬币组合。对每一个这样的组合，计算能凑出至少 $n$ 马克所需的最少硬币数量。在所有这些组合所对应的最少硬币数量中，取其最大值。该最大值即为本题所求的答案。

The single line contains a single integer n (1 ≤ n ≤ 1017).

Please, do not use the %lld specifier to read or write 64 bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

单行包含一个整数 $n$（$1 \leq n \leq 10^{17}$）。

请注意，在 C++ 中读写 64 位整数时，请勿使用 %lld 说明符。推荐使用 cin、cout 流，或 %I64d 说明符。

In a single line print an integer: the maximum number of coins the unlucky buyer could have paid with.

在一行中输出一个整数：不幸的买家可能支付的最多硬币数量。

In the first test case, if a buyer has exactly one coin of at least 3 marks, then, to give Gerald one mark, he will have to give this coin. In this sample, the customer can not have a coin of one mark, as in this case, he will be able to give the money to Gerald without any change.

In the second test case, if the buyer had exactly three coins of 3 marks, then, to give Gerald 4 marks, he will have to give two of these coins. The buyer cannot give three coins as he wants to minimize the number of coins that he gives.

在第一个测试用例中，如果买家恰好拥有一枚面值至少为 3 马克的硬币，那么为了给杰拉尔德 1 马克，他必须给出这枚硬币。在本样例中，顾客不可能拥有一枚面值为 1 马克的硬币，因为此时他将能够在不找零的情况下直接把钱付给杰拉尔德。

在第二个测试用例中，如果买家恰好拥有三枚面值为 3 马克的硬币，那么为了给杰拉尔 4 马克，他必须给出其中两枚硬币。买家不会给出三枚硬币，因为他希望最小化自己所支付的硬币数量。