連分数回路による円周率近似

問題文

分数は連分数展開という、Euclid の互除法に対応する操作で展開することができる。

例えば $\frac{9}{5}$59​ を展開したいとき、$9$9 を $5$5 で割った商は $1$1、余りは $4$4 なので、

$$\frac{9}{5}=1+\frac{4}{5} =1+\frac{1}{\frac{5}{4}}$$59​=1+54​=1+45​1​

となる。次に、$5$5 を $4$4 で割った商は $1$1、余りは $1$1 なので、

$$1+\frac{1}{\frac{5}{4}} = 1+\frac{1}{1+\frac{1}{4}}$$1+45​1​=1+1+41​1​

と連分数展開できる。

今、抵抗 $R$R を用いて、直列接続と並列接続を交互に組み合わせた連分数型の回路を作り、その合成抵抗が $\pi R$πR になるようにしたい。この方法で必要となる抵抗 $R$R の最小の個数 $N$N を求めよ。

制約

• $R=1 \ \Omega$R=1 Ω
• $\pi=\frac{355}{113}$π=113355​

入力形式

$N$N の値を自然数として入力せよ。