题目描述

小理最近发现了一种很有意思的数，把它叫做K-Roliygu数，它的定义如下：

（1）它是一个完全平方数。

（2）它不小于 $10^K$ 。

（3）它的最后一位不为 $0$ 。

（4）如果把它的最后 $K$ 位置零，所得的数仍然是完全平方数。

现在小理的问题来了，给出不大于 $200$ 的正偶整数 $K$ ，如何求一个满足题目的最大K-Roliygu数？

输入格式

题目有多组测试实例。

第一行包含一个正整数 $T$ 表示实例的个数。

每个实例有一行包含一个偶数 $K$ 。

输出格式

对于每个测试实例，输出一行表示最大的K-Roliygu数。

答案可能会很大，所以你只需输出答案模 $2009$ 即可。

如果没有K-Roliygu数或者最大的K-Roliygu数不存在，输出“Oops！”。

样例输入输出

样例输入

1
4

样例输出

197

数据范围

对于 $100%$ 的数据，保证 $T \le 20,2 \le K \le 200$ 。