Double Derangement

You are given two permutations $a$ and $b$, each of length $N$ containing every integer in the range $[1,N]$. Your task is to construct a new permutation $c$ of length $N$ that contains every integer in the range $[1,N]$, such that for every index $i$ ($1$-indexed), the following condition is satisfied:

\[c_i \neq a_i \quad \text{and} \quad c_i \neq b_i.\]

In other words, for no index $i$ can $c_i$ be equal to $a_i$ or $b_i$​.

Given the permutations $a$ and $b$, determine how many such permutations $c$ exist.

The first line of input contains a single integer $T$, denoting the number of test cases.

For each test case, the input is as follows:

• The first line of each test case contains a single integer, $N$, denoting the length of the permutations. ($1 \le N \le 16$)
• The next line contains $N$ space-separated integers, denoting the permutation $a$. Here, the $i$-th integer denotes $a_i$​. ($1 \le a_i \le N;$ $i \ne j \rightarrow a_i \ne a_j$​)
• The next line contains $N$ space-separated integers, denoting the permutation $b$. Here, the $i$-th integer denotes $b_i$​. ($1 \le b_i \le N;$ $i \ne j \rightarrow b_i \ne b_j$)

Sum of $N$ over all cases $\le 2\,000$.

Output how many such permutations $c$ described in the problem exist.

You may have to use a type larger than a $32$-bit integer to prevent overflow in this problem.