Middle-Square Method

Time Limit : 1 sec, Memory Limit : 65536 KB

Middle-Square Method

古典的な乱数生成方法の一つである平方採中法のプログラムを作成します。平方採中法は、フォンノイマンによって1940年代半ばに提案された方法です。

平方採中法は、生成する乱数の桁数をnとしたとき、初期値sの2乗を計算し、その数値を2n桁の数値とみて、(下の例のように2乗した桁数が足りないときは、0を補います。)その中央にあるn個の数字を最初の乱数とします。次にこの乱数を2乗して、同じ様に、中央にあるn個の数字をとって、次の乱数とします。例えば、123を初期値とすると

1232 = 00015129 → 0151
1512  = 00022801 → 0228
2282  = 00051984 → 0519
5192  = 00269361 → 2693
26932  = 07252249 → 2522

の様になります。この方法を用いて、初期値s(10000未満の正の整数)を入力とし、n=4の場合の乱数を10個生成し出力して終了するプログラムを作成してください。

Input

複数のデータセットが与えられます。1行目にデータセットの数 n が与えられます。各データセットは、1行に初期値 s(整数)が与えられます。

Output

各データセットに対して、

Case x: (x は 1 から始まるデータセット番号)
1個目の生成した乱数(整数;半角)
2個目の生成した乱数(整数;半角)
:
:
10個目の生成した乱数(整数;半角)

を出力して下さい。

Sample Input

2
123
567

Output for the Sample Input

Case 1:
151
228
519
2693
2522
3604
9888
7725
6756
6435
Case 2:
3214
3297
8702
7248
5335
4622
3628
1623
6341
2082

Source: PC Koshien 2006 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2006
(extended version)
http://www.pref.fukushima.jp/pc-concours/