A. Nice Perfect Squares
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver calls an integer timely if its decimal representation has $$$2025$$$ as a contiguous substring.

Given an integer $$$N$$$, output any $$$N$$$-digit positive integer $$$X$$$ such that $$$X$$$ is timely and a perfect square. It can be shown that such an integer always exists.

Input

The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 997$$$) — the number of testcases.

The only line of each test case contains a single integer $$$N$$$ ($$$4 \leq N \leq 1000$$$) — the number of digits of $$$X$$$.

Output

For each test case, output an $$$N$$$-digit positive integer $$$X$$$ such that $$$X$$$ is timely and a perfect square.

Example
Input
3
4
5
12
Output
2025
42025
395720257969
Note

In the first test case, $$$2025 = 45^2$$$.

In the second test case, $$$42025 = 205^2$$$.

In the third test case, $$$395720257969 = 629063^2$$$.