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.