Dominoes

import java.awt.Point;
import java.util.Scanner;

public class dominoes {
    public static void debug(Object o) {
        System.out.println("\tDEBUG: " + o.toString().replaceAll("\n", "\n\tDEBUG: "));
    }

    static long modulus = (long) (10e9 + 7);

    public static long factorial(long a)
    {
        long ans = 1;
        for( long i = 2; i <= a; i++ )
        {
            ans *= i;
            ans %= modulus;
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        long T = in.nextInt();
        for (long t = 1; t <= T; t++) {
            int n = in.nextInt();

            Point[] doms = new Point[n];
            for (int i = 0; i < n; i++) {
                doms[i] = new Point(in.nextInt() - 1, in.nextInt() - 1);
            }

            boolean same = true;
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (!(doms[i].equals(doms[j]) || doms[i].equals(new Point(doms[j].y, doms[j].x))))
                        same = false;
                }
            }
            if( same == true )
            {
                System.out.println(factorial(n));
                continue;
            }

            long[][] dp = new long[(1 << n)][6];

            for (int i = 0; i < 6; i++) {
                dp[0][i] = 1;
            }

            for (int i = 0; i < dp.length; i++) {
                for (int d = 0; d < n; d++) {
                    if (((i >> d) & 1) != 0)
                        continue;
                    Point dom = doms[d];

                    int index = i | (1 << d);

                    if( index >= dp.length )
                        continue;

                    // boolean accounted = false;
                    for (int j = 0; j < 6; j++) {
                        /*
                         * if ((dom.x == j || dom.y == j) && index == (int)
                         * Math.pow(2, n) - 1 && accounted == false) { last[d]
                         * += dp[i][j]; accounted = true; }
                         */
                        if (dom.x == j) {
                            dp[index][dom.y] += dp[i][j];
                            dp[index][dom.y] %= modulus;
                        } else if (dom.y == j) {
                            dp[index][dom.x] += dp[i][j];
                            dp[index][dom.x] %= modulus;
                        }
                    }
                }
            }

            long sum = 0;
            for (int i = 0; i < 6; i++) {
                sum += dp[dp.length - 1][i];
                sum %= modulus;
            }

            System.out.println(sum);
        }

        in.close();
    }
}