Truly magical numbers

All submissions for this problem are available.
Prashant thinks that the number 142857 is magical. When he multiplies the number with 2, he gets 285714 which is a permutation of the digits of the original number. On multiplying with 3,4,5 and 6 too he observes a similar behaviour.
Now Prashant wants to find out truly magical numbers. A truly magical number of order N is a number P with the following properties:
 P should have N digits and the first digit should be nonzero
 On multiplying the number with any i such that 1<=i<=k, the result should be a permutation of the digits of P
 There should not exist any N digit number Q (without leading zeros) with the property that for all i such that 1<=i<=k+1, Q*i is a permutation of digits of Q (Here k has the same value as in the previous point)
 N should not have consecutive zero digits anywhere
It is easily seen that P=142857 is indeed a truly magical number of order 6. P has no leading zeros or consecutive zeros appearing anywhere. For 1<=i<=6, P*i is a permutation of digits of P. Also, there does not exist any number Q such that for all 1<=i<=7, Q*i is a permutation of digits of Q.
Given an integer N, find a truly magical number of order N. Note that for certain values of N there may be more than one truly magical number of order N. In such a case, it is enough to output any one of the truly magical numbers of order N.
Input
The first line of input contains an integer T (<=100), the number of test cases to follow.
Following this are T lines, each containing an integer N, 250<=N<=40000
Output
Output T lines, each containing a truly magical number of order N
Example
The input limits are such that an example cannot be shown here. However, to explain the formatting of the input and output, we show here a sample case that has N outside the input limit range
Input: 2 2 6 Output: 13 142857
Author:  razimantv 
Tags  razimantv 
Date Added:  5022011 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, GO, NODEJS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 