Kannondou

Time Limit : 1 sec, Memory Limit : 65536 KB

Kannondou

一郎君の家の裏山には観音堂があります。この観音堂まではふもとから30段の階段があり、一郎君は、 毎日のように観音堂まで遊びに行きます。一郎君は階段を1足で3段まで上がることができます。遊ん でいるうちに階段の上り方の種類(段の飛ばし方の個数)が非常にたくさんあることに気がつきまし た。 そこで一日に10種類の上り方をし、すべての上り方を試そうと考えました。このごろ、一郎君はメタボ リック症候群の話題が気になっていたので、ダイエットと、上り方全種類制覇の一挙両得かと思いまし た。 しかし数学を熟知しているあなたはそんなことでは一郎君の寿命が尽きてしまうことを知っているはず です。そこで、一郎君の計画が実現不可能であることを一郎君に納得させるために、階段の段数nを入 力とし、一日に10種類の上り方をするとして、一郎君がすべての上り方を実行するのに要する年数を出 力するプログラムを作成してください。n は1以上30以下の正の整数とし、一年は365日として計算して ください。一日でも必要なら一年とします。365日なら1年であり、366日なら2年となります。

プログラムは以下に定義する入力が続く限り処理を繰り返し、入力が終わったら終了するように作成し てください。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。 各データセットは以下のとおりです。

1行目 段数 n(整数)

Output

入力データセットごとに一郎君がすべての上り方を実行するのに必要な年数(整数)を出力します。

Sample Input

1
10
20
25
0

Output for the Sample Input

1
1
34
701

Source: PC Koshien 2007 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2007
http://www.pref.fukushima.jp/pc-concours/