The middle-square method is a method used to generate a sequence of pseudorandom numbers. To generate a sequence ~a~ of ~M~-digit numbers, an ~M~-digit number ~a_1~ is chosen as the first number of the sequence. ~a_1~ is squared, producing a ~2M~ digit number (padded with leading zeroes if it has less than ~2M~ digits). The middle ~M~ digits of this square are used to form ~a_2~, the next number in the sequence. This process is then repeated to generate more numbers.

Given ~a_1~, find the next ~4~ numbers in the sequence.

Input Specification

The first line of input will contain a positive even integer ~M~ (~2 \leq M \leq 8~), the number of digits in each number of the sequence.

The second line of input will contain a positive integer ~a_1~, the first number of the sequence. This number might be padded with leading zeroes if it has less than ~M~ digits.

Output Specification

Output the next ~4~ ~M~-digit numbers in the sequence, ~a_2, a_3, a_4, a_5~, each on a separate line, padded with leading zeroes if necessary.

Sample Input 1

6
123456

Sample Output 1

241383
265752
624125
532015

Sample Input 2

4
0123

Sample Output 2

0151
0228
0519
2693