
ZOJ Problem Set  3861
Pattern lock security is generally used in Android handsets instead of a password. The pattern lock can be set by joining points on a 3 × 3 matrix in a chosen order. The points of the matrix are registered in a numbered order starting with 1 in the upper left corner and ending with 9 in the bottom right corner. A valid pattern has the following properties:
Now you are given n active points, you need to find the number of valid pattern locks formed from those active points. InputThere are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case: The first line contains an integer n (3 ≤ n ≤ 9), indicating the number of active points. The second line contains n distinct integers a_{1}, a_{2}, … a_{n} (1 ≤ a_{i} ≤ 9) which denotes the identifier of the active points. OutputFor each test case, print a line containing an integer m, indicating the number of valid pattern lock. In the next m lines, each contains n integers, indicating an valid pattern lock sequence. The m sequences should be listed in lexicographical order. Sample Input1 3 1 2 3 Sample Output4 1 2 3 2 1 3 2 3 1 3 2 1 Author: LIN, Xi Source: The 15th Zhejiang University Programming Contest 