Chef is bored cooking his regular dishes, so he decided to cook permutations instead. Since this is his first time cooking permutations, he takes some help.

Chef has two permutations A and B, each of size N. Chef cooks a permutation C of size N^{2} by doing the following:

for i = 1 to N:
for j = 1 to N:
C[i + (j-1) * N] = A[i] + (B[j] - 1) * N

Chef is allowed to make some (maybe 0) moves on permutation C. In one move, Chef can:
Pick two indices 1 ≤ i < j ≤ N^{2} and swap the elements C_{i} and C_{j}.

Find the minimum number of moves required to sort permutation C in ascending order. 

------ Input Format ------ 

- The first line of the input contains a single integer T - the number of test cases. The description of test cases follows.
- The first line of each test case contains an integer N - the length of permutations A and B.
- The second line of each test case contains N integers A_{1}, A_{2}, \ldots, A_{N}, denoting permutation A.
- The third line of each test case contains N integers B_{1}, B_{2}, \ldots, B_{N}, denoting permutation B.

------ Output Format ------ 

For each test case, print a single integer representing the number of moves required to sort permutation C.

------ Constraints ------ 

$1 ≤T ≤10^{5}$
$1 ≤N ≤2 \cdot 10^{5}$
$1 ≤A_{i}, B_{i} ≤N$
- The sum of $N$ over all test cases doesn't exceed $10^{6}$

------ subtasks ------ 

Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
3
3
3 1 2
2 1 3
2
1 2
1 2
2
2 1
2 1

----- Sample Output 1 ------ 
7
0
2
----- explanation 1 ------ 
- In the first test case, $C = [6, 4, 5, 3, 1, 2, 9, 7, 8]$. Minimum number of moves required to sort permutation $C$ are $7$. 
- In the second test case, $C = [1, 2, 3, 4]$. The permutation is already sorted, so we need $0$ moves.
- In the third test case, $C = [4, 3, 2, 1]$. We need $2$ moves to sort the permutation.

Difficulty: VERY_HARD
Tags: Polynomials and generating functions

Number theory

Matrices

Mathematics

Starter code:

Solutions:
from sys import stdin
from collections import defaultdict
from math import gcd
inp = stdin.readline

def get_cycle_profile():
	prm = tuple((int(s) for s in inp().split()))
	cyc = defaultdict(int)
	vis = [False] * (len(prm) + 1)
	for p in prm:
		if vis[p]:
			continue
		plen = 1
		vis[p] = True
		rov = prm[p - 1]
		while not vis[rov]:
			vis[rov] = True
			plen += 1
			rov = prm[rov - 1]
		cyc[plen] += 1
	return tuple(cyc.items())
T = int(inp())
ans = []
for tx in range(T):
	N = int(inp())
	Acyc = get_cycle_profile()
	Bcyc = get_cycle_profile()
	totcyc = sum((af * sum((gcd(ac, bc) * bf for (bc, bf) in Bcyc)) for (ac, af) in Acyc))
	ans.append(N * N - totcyc)
print(*ans, sep='\n')


from sys import stdin
from collections import defaultdict
from math import gcd

def cycle_prof(prm):
	cyc = defaultdict(int)
	tc = [True] * (len(prm) + 1)
	for p in prm:
		if tc[p]:
			plen = 1
			tc[p] = False
			rov = prm[p - 1]
			while tc[rov]:
				tc[rov] = False
				plen += 1
				rov = prm[rov - 1]
			cyc[plen] += 1
	return tuple(cyc.items())
inp = stdin.readline
T = int(inp())
ans = []
for tx in range(T):
	N = int(inp())
	Acyc = cycle_prof(tuple(map(int, inp().split())))
	Bcyc = cycle_prof(tuple(map(int, inp().split())))
	extcyc = sum((af * sum((gcd(ac, bc) * bf for (bc, bf) in Bcyc)) for (ac, af) in Acyc))
	ans.append(N * N - extcyc)
print(*ans, sep='\n')


from sys import stdin
from collections import defaultdict
from math import gcd

def cycle_prof(prm):
	cyc = defaultdict(int)
	tc = [True] * (len(prm) + 1)
	for p in prm:
		if tc[p]:
			plen = 1
			tc[p] = False
			rov = prm[p - 1]
			while tc[rov]:
				tc[rov] = False
				plen += 1
				rov = prm[rov - 1]
			cyc[plen] += 1
	return cyc
inp = stdin.readline
T = int(inp())
for tx in range(T):
	N = int(inp())
	Acyc = cycle_prof(list(map(int, inp().split())))
	Bcyc = cycle_prof(list(map(int, inp().split())))
	swaps = 0
	for (ac, af) in Acyc.items():
		for (bc, bf) in Bcyc.items():
			g = gcd(ac, bc)
			swaps += (ac * bc - g) * af * bf
	print(swaps)