a, b, c の $3$ 種類の文字からなる文字列 $S$ があります。
Alice は、$S$ に対して「操作 $1$ か操作 $2$ のうち好きな方を実行する」ことを、 どちらの操作も行えなくなるまで 続けます。

• 操作 $1$： $S$ の連続する部分文字列 ba をひとつ選び、aab に置き換える。
• 操作 $2$： $S$ の連続する部分文字列 ca をひとつ選び、aaac に置き換える。

ただし、「 どちらの操作も行えない状態 」とは、 $S$ の連続する部分文字列に ba と ca のどちらも含まれない状態を指します。

Alice の目標は、すべての操作の終了時に、長さ $L$ の文字列を作ることです。
$L$ が与えられるので、目標を達成することが可能である、操作前の文字列 $S$ の長さの最小値を求めてください。

なお、任意の正の整数 $L$ に対して、目標を達成できる文字列 $S$ が存在することが証明できます。

• $1 \leq L \leq 10^{18}$
• $L$ は整数

この問題には、部分点が設定されている。部分点の採点方法については、コンテストトップ を参照すること。

1. ($50$ 点)

• $L \leq 10$

2. ($100$ 点)

• $L \leq 10^3$

3. ($100$ 点)

• $L \leq 10^5$

4. ($400$ 点)

• 追加の制約はない。

入力は以下の形式で標準入力から与えられる。

Alice の目標を達成できる、操作前の文字列 $S$ の長さの最小値を出力せよ。