Weak Goodstain Sequence

問題文

ある正整数 $a$ に対して、以下のよって定義される非負整数列 $A$ を「初項を $a$ とした時の弱グッドスタイン列」と言います。

1. $A=(a)$ とする。
2. $A$ の長さを $k$ とし、 $A_k$ を $(k+1)$ 進数で表す。
3. 2. で表したものを $(k+2)$ 進数で表された整数として解釈する。
4. 3. で得られた値から $1$ を引いた整数を $A$ の末尾に追加する。
5. $A$ の末尾が $0$ でなければ 2. に戻る。（ $A$ の末尾が $0$ であれば処理を終了します。）

正整数 $N$ が与えられます。
初項を $N$ とした時の弱グッドスタイン列 $A$ の長さを求めてください。

ただし、答えは非常に大きくなる可能性があるので、答えが $10^6$ より大きくなる場合は Large と出力してください。

なお、以上で定義される $A$ の長さは、どんな正整数 $N$ から始めても有限になることが証明できます。

制約

• $1\le N\le10^6$
• $N$ は全て整数

入力

出力

非負整数列 $A$ の長さを $1$ 行で出力してください。

入力例1

4

出力例1

22

非負整数列 $A$ は以下の計算により、$(4,8,9,10,11,11,11,11,11,11,11,10,9,8,7,6,5,4,3,2,1,0)$ になります。よって、 $A$ の長さである $22$ を出力してください。

• $A_1=N=4$
• $A_{1}=4=100_{(2)}$ より、$100$ を $3$ 進数で解釈してから $1$ を引いて、$A_{2}=100_{(3)}-1=22_{(3)}=8$
• $A_{2}=8=22_{(3)}$ より、$22$ を $4$ 進数で解釈してから $1$ を引いて、$A_{3}=22_{(4)}-1=21_{(4)}=9$
• $A_{3}=9=21_{(4)}$ より、$21$ を $5$ 進数で解釈してから $1$ を引いて、$A_{4}=21_{(5)}-1=20_{(5)}=10$
• $A_{4}=10=20_{(5)}$ より、$20$ を $6$ 進数で解釈してから $1$ を引いて、$A_{5}=20_{(6)}-1=15_{(6)}=11$
• $A_{5}=11=15_{(6)}$ より、$15$ を $7$ 進数で解釈してから $1$ を引いて、$A_{6}=15_{(7)}-1=14_{(7)}=11$
• $A_{6}=11=14_{(7)}$ より、$14$ を $8$ 進数で解釈してから $1$ を引いて、$A_{7}=14_{(8)}-1=13_{(8)}=11$
• $A_{7}=11=13_{(8)}$ より、$13$ を $9$ 進数で解釈してから $1$ を引いて、$A_{8}=13_{(9)}-1=12_{(9)}=11$
• $A_{8}=11=12_{(9)}$ より、$12$ を $10$ 進数で解釈してから $1$ を引いて、$A_{9}=12_{(10)}-1=11_{(10)}=11$
• $A_{9}=11=11_{(10)}$ より、$11$ を $11$ 進数で解釈してから $1$ を引いて、$A_{10}=11_{(11)}-1=10_{(11)}=11$
• $A_{10}=11=10_{(11)}$ より、$10$ を $12$ 進数で解釈してから $1$ を引いて、$A_{11}=10_{(12)}-1=B_{(12)}=11$
• $A_{11}=11=B_{(12)}$ より、$B$ を $13$ 進数で解釈してから $1$ を引いて、$A_{12}=B_{(13)}-1=A_{(13)}=10$
• $A_{12}=10=A_{(13)}$ より、$A$ を $14$ 進数で解釈してから $1$ を引いて、$A_{13}=A_{(14)}-1=9_{(14)}=9$
• $A_{13}=9=9_{(14)}$ より、$9$ を $15$ 進数で解釈してから $1$ を引いて、$A_{14}=9_{(15)}-1=8_{(15)}=8$
• $A_{14}=8=8_{(15)}$ より、$8$ を $16$ 進数で解釈してから $1$ を引いて、$A_{15}=8_{(16)}-1=7_{(16)}=7$
• $A_{15}=7=7_{(16)}$ より、$7$ を $17$ 進数で解釈してから $1$ を引いて、$A_{16}=7_{(17)}-1=6_{(17)}=6$
• $A_{16}=6=6_{(17)}$ より、$6$ を $18$ 進数で解釈してから $1$ を引いて、$A_{17}=6_{(18)}-1=5_{(18)}=5$
• $A_{17}=5=5_{(18)}$ より、$5$ を $19$ 進数で解釈してから $1$ を引いて、$A_{18}=5_{(19)}-1=4_{(19)}=4$
• $A_{18}=4=4_{(19)}$ より、$4$ を $20$ 進数で解釈してから $1$ を引いて、$A_{19}=4_{(20)}-1=3_{(20)}=3$
• $A_{19}=3=3_{(20)}$ より、$3$ を $21$ 進数で解釈してから $1$ を引いて、$A_{20}=3_{(21)}-1=2_{(21)}=2$
• $A_{20}=2=2_{(21)}$ より、$2$ を $22$ 進数で解釈してから $1$ を引いて、$A_{21}=2_{(22)}-1=1_{(22)}=1$
• $A_{21}=1=1_{(22)}$ より、$1$ を $23$ 進数で解釈してから $1$ を引いて、$A_{22}=1_{(23)}-1=0_{(23)}=0$

入力例2

1000000

出力例2

Large

初項を $10^6$ から始めた場合は非負整数列 $A$ の長さは $10^6$ を超えます。

入力例3

1

出力例3

2