砝码称重

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

给你一些砝码,砝码的重量为1,3,9,27……(3^m),每个砝码都有无数多个。然后给你一架天平,一个物品,问你至少需要使用多少个砝码能称出物品的重量。

Input

多组测试样例,每组测试样例输入一个数n(0<n<2^31)表示物品的重量。

Output

对于每组测试样例输出至少需要使用砝码的数量。

Sample Input

4
7
9

Sample Output

2
3
1

Hint

物品放一边,砝码放另一边。

Source

huangwei

提交代码