ارسال شماره 963

import java.util.*;
 
public class Main {
 
    // between[a][b] = midpoint node between a and b (1-indexed), or 0 if none
    private static final int[][] BETWEEN = new int[10][10];
 
    static {
        int[] row = {0, 0,0,0, 1,1,1, 2,2,2};
        int[] col = {0, 0,1,2, 0,1,2, 0,1,2};
 
        for (int a = 1; a <= 9; a++) {
            for (int b = 1; b <= 9; b++) {
                if (a == b) continue;
                int dr = row[b] - row[a];
                int dc = col[b] - col[a];
                // midpoint exists only when both deltas are even
                if (dr % 2 == 0 && dc % 2 == 0) {
                    int mr = row[a] + dr / 2;
                    int mc = col[a] + dc / 2;
                    // find which node is at (mr, mc)
                    for (int n = 1; n <= 9; n++) {
                        if (row[n] == mr && col[n] == mc) {
                            BETWEEN[a][b] = n;
                            break;
                        }
                    }
                }
            }
        }
    }
 
    private static int count;
    private static boolean[] required;
 
    public static int countPatterns(int[] requiredNodes) {
        required = new boolean[10];
        for (int n : requiredNodes) required[n] = true;
 
        count = 0;
        boolean[] visited = new boolean[10];
 
        for (int start = 1; start <= 9; start++) {
            visited[start] = true;
            backtrack(start, visited, 1);
            visited[start] = false;
        }
 
        return count;
    }
 
    private static void backtrack(int last, boolean[] visited, int visitedCount) {
        // check if all required nodes are visited
        boolean allRequired = true;
        for (int n = 1; n <= 9; n++) {
            if (required[n] && !visited[n]) {
                allRequired = false;
                break;
            }
        }
        if (allRequired) count++;
 
        for (int nxt = 1; nxt <= 9; nxt++) {
            if (visited[nxt]) continue;
            int mid = BETWEEN[last][nxt];
            // if there's a midpoint node that hasn't been visited, move is blocked
            if (mid != 0 && !visited[mid]) continue;
 
            visited[nxt] = true;
            backtrack(nxt, visited, visitedCount + 1);
            visited[nxt] = false;
        }
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        StringBuilder sb = new StringBuilder();
 
        while (T-- > 0) {
            int k = sc.nextInt();
            int[] required = new int[k];
            for (int i = 0; i < k; i++) required[i] = sc.nextInt();
            sb.append(countPatterns(required)).append('\n');
        }
 
        System.out.print(sb);
    }
}