Unlock my safe#6953
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 *, #, and in my password.
Each digit in the password is distinct. That is, they never appear more than once.
My password is at most digits (1 \leq n \leq 8, where is a number of digits in the password).
Each digit in the password always has the value less than or equal to (that is, a password is valid for n = 3 but a password such as is invalid because the third digit exceeds ).
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 in the sorted array of permutations, where 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 (not ).
Write a program to find a correct password for a given length (a number of digits in the password).
The first line contains an integer (1 \leq t \leq 6) denoting the number of test cases. After that test cases follow. Each test case contains an integer (1 \leq n \leq 8) denoting a number of digits in a password.
Your program should output the -digit password for each corresponding test case, one password per line.
Example 1
There are test cases above. In the second case, for example, the sorted permutations are {, , , , , }. Password is located at the position 6 \backslash 3 = 2 (integer division). When the starting index begins at , the password is, therefore, .