순열 그래프

그래프 $G$는 정점의 집합 $V$와 간선의 집합 $E$로 이루어지고, $G = (V, E)$로 쓴다. 보통은 두 집합을 그대로 나열해서 그래프를 정의하지만, 간선을 나열하는 대신 만드는 규칙만 정해 두는 그래프도 있다. 순열 그래프가 그렇다.

$\{1, 2, \dots, n\}$의 순열 두 개를 준비한다. 평행한 직선을 두 개 긋고, 위쪽 직선에는 첫 번째 순열의 순서대로, 아래쪽 직선에는 두 번째 순열의 순서대로 숫자를 왼쪽부터 놓는다. 그 다음 같은 숫자끼리 선분으로 잇는다. 이렇게 그은 선분 중 서로 교차하는 쌍이 순열 그래프의 간선이 되고, 정점은 $1$부터 $n$까지의 숫자다.

두 순열이 $(2, 5, 4, 1, 3)$과 $(1, 5, 3, 2, 4)$인 경우 교차하는 선분의 쌍은 여섯 개이므로, 순열 그래프는 $V = \{1, 2, 3, 4, 5\}$, $E = \{(1,2), (1,4), (1,5), (2,3), (2,5), (3,4)\}$가 된다.

$\{1, 2, \dots, n\}$의 순열 두 개가 주어졌을 때, 두 순열로 만든 순열 그래프의 간선의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 세 줄이다. 첫째 줄에 $n$이 주어지고 $(1 \le n \le 100{,}000)$, 둘째 줄과 셋째 줄에 순열이 하나씩 주어진다. 두 순열 모두 $\{1, 2, \dots, n\}$의 순열이고, 원소는 공백으로 구분된다.

각 테스트 케이스마다 두 순열로 만든 순열 그래프의 간선의 개수를 한 줄에 하나씩 출력한다.