同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

21660_SquareNumberAgain

2022-5-16 18:20| 发布者: Hocassian| 查看: 26| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-4-89505734800400-Problem List-采集的数据-后羿采集器.html

Pro.ID

21660

Title

Square Number Again

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=21660

AC

Submit

Ratio

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

Square number is very popular in ACM/ICPC. Now here is a problem about square number again.

Let's consider such a kind of number called K-Omitted-Square-Number (K-OSN). N is a K-OSN if:

(1) It is a square number.

(2) Its last digit is not 0.

(3) It's not less than 10^K.

(4) If its last K digits are omitted, it's still a square number.

Now, given an even number K, you have to find the largest K-OSN.

输入

There are multiple test cases in this problem.

The first line will contain a single positive integer T ( T ≤ 20 ) indicating the number of test cases. Each test case will be a single line containing an even number K ( 2 ≤ K ≤ 200 ).

输出

Description

Square number is very popular in ACM/ICPC. Now here is a problem about square number again.

Let's consider such a kind of number called K-Omitted-Square-Number (K-OSN). N is a K-OSN if:

(1) It is a square number.

(2) Its last digit is not 0.

(3) It's not less than 10^K.

(4) If its last K digits are omitted, it's still a square number.

Now, given an even number K, you have to find the largest K-OSN.

Input

There are multiple test cases in this problem.

The first line will contain a single positive integer T ( T ≤ 20 ) indicating the number of test cases. Each test case will be a single line containing an even number K ( 2 ≤ K ≤ 200 ).

Output

For each test case, print a single line containing the largest K-OSN. In case that it will be very large, you just need to print the number modulo 2009. If there are no K-OSN, or if the largest K-OSN doesn't exist, print "Oops!" (without quotes).

Sample Input

1
4

Sample Output

197

Source

ZS 2009 pre