三分木棍

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

现在有一根长度为 n 木棍,Fish 需要把它掰成若干个长度小于 3 的小木棍。

Fish 决定使用三分法去掰这根木棍,三分法的操作如下。

 

第一步:如果这根木棍长度小于 3,那么不需要掰了,否则就进入下一步。

第二步:对于长度大于三的木棍,Fish 将他掰成三段,长度分别为 (n / 3), (n / 3), (n - n / 3 * 2),这里除法为下取整。

第三步:对于第二步得到的新的小木棍,分别去执行第一步操作。

 

对于长度为 7 的木棍,那么他会在第二步掰成 2, 2, 3。长度为 5 的木棍,第二步会被掰成 1,1,3。

 

现在 Fish 执行这个三分法去掰木棍后,最后会得到几个长度小于 3 的小木棍。

Input

多组输入:

    每组数据输入一包含一个 n 为初始的木棍长度。(1 <= n <= 1000)

Output

每组输出一行包含一个整数,为掰完后的小木棍个数。

Sample Input

1
3
5
7
9

Sample Output

1
3
5
5
9

Hint

Source

【2017级《程序设计基础(B)II》中外期末上机考试】Fish