Counting Leaves in a Ternary-Digit Tree

Consider a special rooted tree built from a given number \( x \) as follows:

• The root node is \( \langle 0, x \rangle \).
• For any node \( \langle i, j \rangle \), if \( j < 3 \) then it is a leaf node. Otherwise, if \( j \ge 3 \), let \( j_1 j_2 \dots j_n \) be the ternary (base-3) representation of \( j \) (with \( n \) being the number of digits). Then for each integer \( k \) (\( 1 \le k \le n \)), the node has a child \( \langle j_k, k \rangle \), where \( j_k \) is the \( k\text{-th} \) digit (from left) in the ternary representation of \( j \).

Your task is to determine the total number of leaf nodes of the tree.

Observation: Notice that if \( x < 3 \), the root is a leaf. Otherwise, note that every child of the root has its second value equal to a digit of the base-3 representation of \( x \), and since every digit in base 3 is in \( \{0,1,2\} \), all children become leaves. Therefore, when \( x \ge 3 \), the number of leaf nodes is exactly the number of digits in the ternary representation of \( x \).

Note: The time-space limits may be unusual!

inputFormat

The input consists of a single integer \( x \) provided on one line.

outputFormat

Output a single integer representing the number of leaf nodes in the tree.

sample

2

1