题目描述

对于任意非负整数 $x$，定义函数 $f(x)$：

$$f(x)= \begin{cases} 1 & (x=0)\\ f(\lfloor\frac{x}{3}\rfloor)+1 & (x>0 \text{ 且 } x \bmod 3=0)\\ f(x-1)+1 & (x>0 \text{ 且 } x \bmod 3 \ne 0) \end{cases}$$

其中 $\lfloor\cdot\rfloor$ 代表向下取整运算，$\bmod$ 代表取模运算。

你的任务很简单，给定任意非负整数 $x$，请输出 $f(x)$ 的值。

题目格式

输入格式

输入仅有一行，包含一个非负整数 $x(1\le x\le 10^5)$，表示询问参数。

输出格式

输出仅有一行，包含一个整数，表示 $f(x)$ 的值。

样例

6

4

520

12

1816

15