操作 \(4 \rightarrow 3 \rightarrow 4 \rightarrow 3 \rightarrow \cdots\) と続けることを考えます． ここで，操作を合計 \(S\) 回行ったとします． 便利のため，\(S\) は偶数であるとします．

任意の \(i\) (\(0 \leq i \leq S\)) について，\(i\) 回目の操作後に操作 \(1\) か操作 \(2\) を行うことを考えます． すると，以下のことがわかります．

• \(i\) が偶数の場合：操作 \(1\) を \(1\) 回行うたびに，最終的な \(x\) の値が \(fib(S-i)\) 増える．
• \(i\) が奇数の場合：操作 \(2\) を \(1\) 回行うたびに，最終的な \(x\) の値が \(fib(S-i)\) 増える．

ただしここで，\(fib(n)\) はフィボナッチ数(\(fib(0)=1,fib(1)=1,fib(n)=fib(n-1)+fib(n-2) \) for \(2 \leq n\))を表します．

各 \(i\) について，高々 \(1\) 回だけ操作 \(1\) or \(2\) を行うことを考えてみます． この場合，\(S\) の値としては，\(fib(S) \leq 10^{18}\) となる最大の \(S\) を選べばよいです．それ以上大きい \(S\) は無駄であるためです． 実際に計算すると \(S=86\) を選べばよいとわかります．

あとは，\(fib(S-i)\) の和で \(N\) を作る問題を解けばよいです． これは，\(i\) の小さい方から，操作が行えるなら行う貪欲をすればよいです． この時，\(i\) と \(i+1\) 両方で操作することはありません． なぜなら，その場合は \(i-1\) で操作すればいいからです． よって，操作 \(1\) or \(2\) の回数は \(S/2+1=44\) で抑えられます． （なお，実際には最大で \(43\) 回です）

よって，全体の操作回数が \(86+44=130\) 回で抑えられ，この問題が解けます．