acm International Collegiate Programming Contest

Links

A B C D E F G H

Problem C

竹の花

竹の寿命は数十年あり,一生の最後に花を咲かせて種をつくる. 筑波を旅行していた生物学者の ACM 博士は偶然見かけた竹の花の美しさに魅了され, 竹の花を毎年見られる庭を作りたいと思った. ACM 博士は,竹の品種改良をはじめて,ついに竹の寿命を操作した品種を作る方法を確立した. この方法を使えば,任意の年数で花を咲かせる竹の品種を作ることができる.

種をまいてから k 年で花を咲かせる竹を k 年竹と呼ぶことにしよう. k 年竹は種をまいてから k 年で種を作って枯れる. したがって,さらに k 年後には次の世代が花を咲かせる. このように,k 年竹の種をまくと,k 年周期で花が見られる. 例えば, 15 年竹の種をまくと, 15 年後,30 年後,45 年後というように 15 年ごとに花が見られる.

あなたは,ACM 博士に庭の設計を依頼された.庭はいくつかの区画に区切られている. 1 つの区画では同じ品種の竹しか育てることができない. ACM 博士の依頼は,できるだけ多くの年にどこかの区画で竹の花を見るには, 各区画にどの品種の竹の種をまけばよいかを決めて欲しいというものである.

あなたは,すぐに全ての区画に1年竹の種をまくことを提案した. しかし,ACM 博士によれば寿命の短い竹の品種は作るのが難しいので, 寿命が長い竹だけしか使わない庭を設計して欲しいそうだ. 最初の竹が咲くまで待つのはかまわないが, その後は毎年花が見られるようにして欲しいということだ. 今度は,例えば 10 年竹を使って,今年はある区画に,来年は別区画にというように, 10 年間異なる区画にまき続けることを提案した.そうすれば, 10 年後以降毎年どこかの区画で花が見られる.しかし ACM 博士は, もう全区画に今年種をまくと決めたのだ,と反対した.

そこであなたは,

  • m 年以上の寿命の竹だけを使い,
  • すべての区画に今年種をまく
という条件で,m 年後以降できるだけ長い期間どこかの区画では花が咲くような種のまき方を考えることにした.

Input

入力は最大で 50 個のデータセットからなる. 各データセットは次の形式で表される.

m n

整数 m (2 ≤ m ≤ 100) は造園に使える最短の寿命の竹の寿命(年)である. 整数 n (1 ≤ n ≤ 500,000) は区画の数である.

入力の終わりは 2 つのゼロからなる行で表される.

Output

いくらよい計画を作っても,どの区画でも花が咲かない「退屈な年」がいつか必ずやってくる. 各データセットについて, m 年目以降で初めて訪れる退屈な年が今から何年後かを示す整数だけからなる行を出力せよ.

なお, m = 2, n = 500,000 (Sample Input の最後のデータセット)のとき答が最大となる.

Sample Input

3 1
3 4
10 20
100 50
2 500000
0 0

Output for the Sample Input

4
11
47
150
7368791
(End of Problem C) A B C D E F G H