시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)3431829957.895%

문제

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.

서브태스크 1 (40점)

Modified constraints apply: $1 \le N \le 8;$ Sum of $N$ over all cases $\le 1\,000$.

서브태스크 2 (40점)

Modified constraints apply: $1 \le N \le 16;$ $\boldsymbol{\underline{a=b}},$ i.e., the permutation $a$ and $b$ is same for all indices $1 \le i \le N;$ Sum of $N$ over all cases $\le 2\,000$.

서브태스크 3 (20점)

Original constraints apply: $1 \le N \le 16;$ Sum of $N$ over all cases $\le 2\,000$.

예제 입력 1

1
4
1 2 3 4
2 3 1 4

예제 출력 1

3

There are $3$ such permutations:

\[[3,1,4,2] \qquad [3,4,2,1] \qquad [4,1,2,3]\]

노트

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

채점 및 기타 정보

  • 예제는 채점하지 않는다.