Tokitsukaze has two colorful tapes. There are $n$ distinct colors, numbered $1$ through $n$, and each color appears exactly once on each of the two tapes. Denote the color of the $i$-th position of the first tape as $ca_i$, and the color of the $i$-th position of the second tape as $cb_i$.

Now Tokitsukaze wants to select each color an integer value from $1$ to $n$, distinct for all the colors. After that she will put down the color values in each colored position on the tapes. Denote the number of the $i$-th position of the first tape as $numa_i$, and the number of the $i$-th position of the second tape as $numb_i$.

For example, for the above picture, assuming that the color red has value $x$ ($1 \leq x \leq n$), it appears at the $1$-st position of the first tape and the $3$-rd position of the second tape, so $numa_1=numb_3=x$.

Note that each color $i$ from $1$ to $n$ should have a distinct value, and the same color which appears in both tapes has the same value.

After labeling each color, the beauty of the two tapes is calculated as $$\sum_{i=1}^{n}|numa_i-numb_i|.$$

Please help Tokitsukaze to find the highest possible beauty.


-----Input-----

The first contains a single positive integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

For each test case, the first line contains a single integer $n$ ($1\leq n \leq 10^5$) — the number of colors.

The second line contains $n$ integers $ca_1, ca_2, \ldots, ca_n$ ($1 \leq ca_i \leq n$) — the color of each position of the first tape. It is guaranteed that $ca$ is a permutation.

The third line contains $n$ integers $cb_1, cb_2, \ldots, cb_n$ ($1 \leq cb_i \leq n$) — the color of each position of the second tape. It is guaranteed that $cb$ is a permutation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^{5}$.


-----Output-----

For each test case, print a single integer — the highest possible beauty.


-----Examples-----

Input
3
6
1 5 4 3 2 6
5 3 1 4 6 2
6
3 5 4 6 2 1
3 6 4 5 2 1
1
1
1
Output
18
10
0


-----Note-----

An optimal solution for the first test case is shown in the following figure:

The beauty is $\left|4-3 \right|+\left|3-5 \right|+\left|2-4 \right|+\left|5-2 \right|+\left|1-6 \right|+\left|6-1 \right|=18$.

An optimal solution for the second test case is shown in the following figure:

The beauty is $\left|2-2 \right|+\left|1-6 \right|+\left|3-3 \right|+\left|6-1 \right|+\left|4-4 \right|+\left|5-5 \right|=10$.

Difficulty: HARD
Tags: Greedy algorithms

Graph algorithms

Graph traversal

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline
mod = 1000000007
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	brr = [int(x) for x in input().split()]
	iarr = [0] * (n + 1)
	ibrr = [0] * (n + 1)
	for i in range(n):
		iarr[arr[i]] = i
		ibrr[brr[i]] = i
	ans = []
	vst = [False] * (n + 1)
	for i in range(n):
		if vst[i]:
			continue
		if arr[i] == brr[i]:
			vst[i] = True
			continue
		a = arr[i]
		b = brr[i]
		vst[i] = True
		cnt = 1
		while b != arr[i]:
			vst[iarr[b]] = True
			a = b
			b = brr[iarr[b]]
			cnt += 1
		ans.append(cnt)
	ans.sort(reverse=True)
	(a, b) = (1, n)
	rev = 0
	for num in ans:
		oa = a
		ob = b
		a += num // 2
		b -= num // 2
		rev += (ob - oa + (b - a + 2)) * (num // 2)
	print(rev)


t = int(input())
for _ in range(t):
	n = int(input())
	nums_a = [int(x) for x in input().split()]
	nums_b = [int(x) for x in input().split()]
	map_a_b = {}
	for (x, y) in zip(nums_a, nums_b):
		if x != y:
			map_a_b[x] = y
	new_cnt = 0
	for num in list(map_a_b.keys()):
		if map_a_b[num] != num:
			tmp = num
			cnt = 0
			while map_a_b[tmp] != tmp:
				new_tmp = map_a_b[tmp]
				map_a_b[tmp] = tmp
				tmp = new_tmp
				cnt += 1
			new_cnt += cnt // 2
	print(2 * (n - new_cnt) * new_cnt)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	p = {a[i]: int(s) for (i, s) in enumerate(input().split())}
	vis = [0 for _ in range(n)]
	k = 1
	max = n - 1
	ans = 0
	for u in range(n):
		if vis[u] != 0:
			continue
		cur = u
		cnt = 0
		while vis[cur] == 0:
			vis[cur] = k
			cur = p[cur + 1] - 1
			cnt += 1
			if cnt % 2 == 0:
				ans += max
				max -= 2
	ans *= 2
	print(ans)


f = lambda : input().strip()
t = int(f())
for _ in range(t):
	n = int(f())
	a = [int(x) for x in f().split(' ')]
	g = {a[i]: int(x) for (i, x) in enumerate(f().split(' '))}
	del a
	u = [0 for _ in range(n)]
	i = 0
	k = 1
	answer = 0
	max_dist = n - 1
	for i in range(n):
		if u[i] != 0:
			continue
		j = i
		cl = 0
		while u[j] == 0:
			u[j] = k
			j = g[j + 1] - 1
			cl += 1
			if cl % 2 == 0:
				answer += max_dist
				max_dist -= 2
		k += 1
	answer *= 2
	print(answer)


def dfs(node, adj, vis):
	current = node
	path_length = 0
	while current != -1:
		path_length += 1
		vis[current] = True
		next = -1
		for i in adj[current]:
			if not vis[i]:
				next = i
				break
		current = next
	return path_length

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	adj = [[] for _ in range(n + 1)]
	for i in range(n):
		if a[i] != b[i]:
			u = a[i]
			v = b[i]
			adj[u].append(v)
			adj[v].append(u)
	l = []
	vis = [False for _ in range(n + 1)]
	for i in range(1, n + 1):
		if not vis[i]:
			val = dfs(i, adj, vis)
			l.append(val)
	positives = sum([val // 2 for val in l])
	negatives = sum([val // 2 for val in l])
	if positives == 0:
		print(0)
		return
	x = [i + 1 for i in range(n)]
	pos = x[-positives:]
	neg = x[:negatives]
	pos_val = sum(pos)
	neg_val = sum(neg)
	print(2 * (pos_val - neg_val))
TESTS = int(input())
while TESTS:
	solve()
	TESTS -= 1


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	ca = list(map(int, input().split()))
	cb = list(map(int, input().split()))
	graph = [[] for _ in range(n)]
	colorPos = [[] for _ in range(n)]
	for i in range(n):
		(pa, pb) = (ca[i], cb[i])
		colorPos[pa - 1].append(i)
		colorPos[pb - 1].append(i)
	for i in range(n):
		(p1, p2) = colorPos[i]
		graph[p1].append(p2)
		graph[p2].append(p1)
	arr = []
	vis = set()
	for i in range(n):
		if i not in vis:
			stack = [i]
			num1 = len(vis)
			vis.add(i)
			while stack:
				curr = stack.pop()
				for nei in graph[curr]:
					if nei not in vis:
						vis.add(nei)
						stack.append(nei)
			num2 = len(vis)
			arr.append(num2 - num1)
	arr.sort(reverse=True)
	ans = 0
	(f, b) = (1, n)
	for num in arr:
		if num == 1:
			continue
		ans += (b - f) * (num - 1) - (num - 2) * (num - 1) // 2
		ans += b - num // 2 + 1 - f if num % 2 == 0 else num // 2
		f += num // 2
		b -= num // 2
	return ans
for _ in range(int(input())):
	print(solve())