슈퍼제곱수

시간 제한1초메모리 제한128 MB

요약

각 n에 대해 전체와 앞뒤 n자리 부분이 모두 0이 아닌 완전제곱수인 가장 작은 2n자리 수를 구한다.

문제

자연수 $B$ 가 존재하여 $B \times B = A$ 를 만족하면, 양의 정수 $A$ 를 완전제곱수라고 한다.

양의 정수 $n$ 을 고정하자. 앞에 0이 붙지 않는 $2n$ 자리 수가 다음 세 조건을 모두 만족하면 이를 슈퍼제곱수라고 한다.

뒤쪽 $n$ 자리로 이루어진 수는 앞에 0이 올 수 있으나, 그 값이 $0$ 이어서는 안 된다.

모든 $2n$ 자리 슈퍼제곱수 중 가장 작은 수를 출력하여라. $2n$ 자리 슈퍼제곱수가 존재하지 않으면 대신 NO SUPERSQUARE POSSIBLE 을 출력한다.

첫째 줄에 테스트 케이스의 수 $T$ ( $1 \le T \le 10$ )가 주어진다.

다음 $T$ 개의 줄에 각각 정수 $n$ ( $1 \le n \le 500$ )이 하나씩 주어진다.

입력과 같은 순서로, 테스트 케이스마다 한 줄씩 총 $T$ 줄을 출력한다.

각 $n$ 에 대하여 가장 작은 $2n$ 자리 슈퍼제곱수를 출력한다. 그러한 수가 존재하지 않으면 그 줄에 NO SUPERSQUARE POSSIBLE 을 출력한다.