問題文

占いの一種である数秘術において、「運命数」という概念があります。

運命数とは、年月日の各桁を全て足し合わせる操作をその和が1桁になるか、2桁のゾロ目になるまで繰り返す事で求められます。

例えば、2023年2月15日の運命数は、2+0+2+3+0+2+1+5=152+0+2+3+0+2+1+5=151+5=61+5=6となり、2085年12月31日の運命数は、2+0+8+5+1+2+3+1=222+0+8+5+1+2+3+1=22となります。

運命数NNと年月日を表す8桁の文字列SSが与えられるので、与えられた年月日以降に最も早く現れる、運命数がNNである年月日を出力してください。

ただし、うるう年は考慮しないものとし、問題で使用する各月の日数は以下の通りとします。

  • 1, 3, 5, 7, 8, 10, 12月 → 31日
  • 4, 6, 9, 11月 → 30日
  • 2月 → 28日

制約

  • NN19,11,22,33,441~9, 11, 22, 33, 44のいずれかである
  • 与えられる年月日の範囲は2000年1月1日~2999年12月31日であり、グレゴリオ暦において存在する年月日である
  • 月日が2月29日であるケースは与えられない

入力

11行目では整数NNが与えられる。

22行目では"YYYYMMDD"形式でゼロ埋めされた、年月日を表す8桁の文字列SSが与えられる。

N
S

出力

計算結果を入力の形式と同様に、ゼロ埋めされた8桁の文字列を一行に出力せよ。

サンプル

入力1
8
20231223
出力1
20231225

2023年12月23日の運命数は66です。その2日後である2023年12月25日の運命数は88であり、これは2023年12月23日以降、最も早く現れる運命数88の年月日です。

入力2
7
20280702
出力2
20280706

入力と同様の形式で出力してください。

入力3
5
20060204
出力3
20060204

以降は当日を含むため、与えられた年月日と出力する答えが同じになる場合があります。

入力4
11
20350902
出力4
20350919

各桁の和が1桁になるか2桁のゾロ目になるまで操作を行う必要がある事に注意してください。

Submit


Go (1.21)