Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0112 - UNLOCK MY SAFE

   I forgot the password to my safe. There is a lot of money in it! Please help me unlock the safe. The keypad looks like this.

   I do not remember how long my password is. Hence, you need to try a different length of the password. However, there are some hints that I can recall.

  • I never use characters *, #, 0 and 9 in my password.
  • Each digit in the password is distinct. That is, they never appear more than once.
  • My password is at most 8 digits (1 <= N <= 8, where N is a number of digits in the password).
  • Each digit i in the password always has the value less than or equal to N (that is, a password 132 is valid for N = 3 but a password such as 124 is invalid because the 3rd digit exceeds 3).

   Use the information above and generate all possible permutations. One permutation corresponds to one guess of a password to unlock my safe. Importantly, the correct password is deliberately fixed at position L\3 in the sorted array of permutations, where L is a number of all possible permutations and ‘\’ is an integer division. The sorted array of permutations is in ascending order and the starting index in the sorted array begins at 0 (not 1). 

   Write a program to find a correct password for a given length (a number of digits in the password).

Input

   The first line of the input contains an integer T (1 <= T <= 6) denoting the number of test cases.   After that T test cases follow. Each test case contains an integer N (1 <= N <= 8) denoting a number of digits in a password.

Output

   Your program should output the N-digit password for each corresponding test case, one password per line.

Examples

stdin

stdout

1

3

2

3

1

12

213

1

 


Ավելացրեց.Հրանտ Հովհաննիսյան (ԳՏՏԿ)
Ամսաթիվ.2014-02-01
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.Thailand Southern 2013.A

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.