Jinkoki

Time Limit : 1 sec, Memory Limit : 65536 KB

塵劫記

大きな数を表そうとすると、文字数も多くなるし、位取りがわからなくなってしまうので、なかなか面倒です。大きな数をわかりやすく表すために、人々は数の単位を使ってきました。江戸時代に書かれた「塵劫記」という本の中では、数の単位が次のように書かれています。


たとえば、2の100乗のようなとても大きな数は、126穣7650(じょ)6002垓2822京9401兆4967億320万5376と表せます。それでは、正の整数 mn が与えられたとき、mn 乗を塵劫記の単位を使って上のように表すプログラムを作成してください。

入力

入力は複数のデータセットからなる。入力の終わりはゼロ2つの行で示される。各データセットは以下の形式で与えられる。

m n

m (2 ≤ m ≤ 20) が基数、n (1 ≤ n < 240) が指数を表す。ただし、mnは 1072 未満である。

データセットの数は 100 を超えない。

出力

データセットごとに、mn を塵劫記の単位で表した文字列を1行に出力する。ただし、各単位は以下の表記で出力する。


mnを表す文字列は、1 から 9999 までの数と上の表に現れる単位を表す文字列からなる。文字列には、余分な 0 や単位を含めない。

入出力例


入力例

2 10
5 20
10 8
20 17
0 0

出力例

1024
95Cho3674Oku3164Man625
1Oku
131Gai720Kei

Source: PC Koshien 2013 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2013-11-9
http://web-ext.u-aizu.ac.jp/pc-concours/