This is a problem from 2021 ICPC Shannxi invitational and confuse me a lot. Since this contest have neither place to up-solving nor tutorial, I'm here to ask for idea and help.

The problem is like:

Given a number X, we call another number N is a lucky number to X if:

1. N is larger than 1e8;
2. N is smaller than 1e13;
3. (N!) begins with X.

For example, if we ignore the first constraint, N=10 is a lucky number to X=3628 since (10!)=3628800.

Now, given T testcases, each testcases gives you a X, output any N where N is a lucky number to X.

T is smaller than 200 and X is smaller than 1e5.

Sample input

2 494 997

Sample output

1000001586369 1000001980150