Description

Among $n$ coins that look identical, find one counterfeit coin. There is a balance scale without markings that can show whether the weights on both sides are equal. If they are equal, the scale will not tilt; if they are not equal, the heavier side will tilt. Design an efficient algorithm to find the counterfeit coin. Assume that the counterfeit coin is lighter than the genuine coins.

Input Format

The input consists of multiple lines, each containing the number of coins $n$, $1≤n≤2303$. The program ends when $0$ is entered.

Output Format

Output the minimum number of weighings needed to definitely find the counterfeit coin. The output corresponds to the number of input lines.

Sample

16
0

3