Supersquare

Time limit1sMemory limit128 MB

Summary

For each n, find the smallest 2n-digit number whose full value and both n-digit halves are nonzero perfect squares.

Level: Medium7 of 10
Topics: Math, Number theory, Brute force, Implementation
Solved: No attempts yet

Problem

A positive integer $A$ is a perfect square when some natural number $B$ satisfies $B \times B = A$ .

Fix a positive integer $n$ . A $2n$ -digit number, written without leading zeroes, is a supersquare when all three conditions hold:

the whole $2n$ -digit number is a perfect square;
the number formed by its first (leftmost) $n$ digits is a perfect square;
the number formed by its last (rightmost) $n$ digits is a perfect square.

The number formed by the last $n$ digits may contain leading zeroes, but it must not equal $0$ .

Among all $2n$ -digit supersquares, print the smallest one. If no $2n$ -digit supersquare exists, print the phrase NO SUPERSQUARE POSSIBLE instead.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 10$ ).

Each of the next $T$ lines contains one integer $n$ ( $1 \le n \le 500$ ).

Output

Print $T$ lines, one per test case, in the same order as the input.

For each $n$ , print the smallest $2n$ -digit supersquare. If no such number exists, print NO SUPERSQUARE POSSIBLE on that line.

Examples2

Example 1
Input
```
2
1
2
```
Expected output
```
49
1681
```
Example 2
Input
```
3
3
4
5
```
Expected output
```
144400
24019801
1299602500
```