시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 9 | 9 | 6 | 100.000% |
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.
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).
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.
Your program should output the N-digit password for each corresponding test case, one password per line.
3 2 3 1
12 213 1
There are 3 test cases above. In the second case, for example, the sorted permutations are {123, 132, 213, 231, 312, 321}. Password is located at the position 6\3 = 2 (integer division). When the starting index begins at 0, the password is, therefore, 213.