Double Derangement

You are given two permutations $a$ and $b$, each of length $N$. Each permutation contains every integer in the range $[1, N]$ exactly once. 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 holds.

$c_i \ne a_i \quad \text{and} \quad c_i \ne b_i$

In other words, $c_i$ can never equal $a_i$ or $b_i$ at the same index. Given $a$ and $b$, count the permutations $c$ that satisfy this condition.

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

Each test case is given as follows. The first line contains a single integer $N$, the length of the permutations. The next line contains $N$ space-separated integers, the permutation $a$, where the $i$-th integer is $a_i$. The next line contains $N$ space-separated integers, the permutation $b$, where the $i$-th integer is $b_i$.

Constraints: $1 \le N \le 16$; $1 \le a_i \le N$; $1 \le b_i \le N$; within each permutation, all values are distinct. The sum of $N$ over all test cases is at most $2{,}000$.

For each test case, output the number of permutations $c$ that satisfy the condition.

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