Beppa and her circle of geek friends keep up to date on a group chat in the instant messaging app SwerChat$^{\text{TM}}$.

The group has $n$ members, excluding Beppa. Each of those members has a unique ID between $1$ and $n$. When a user opens a group chat, SwerChat$^{\text{TM}}$ displays the list of other members of that group, sorted by decreasing times of last seen online (so the member who opened the chat most recently is the first of the list). However, the times of last seen are not displayed.

Today, Beppa has been busy all day: she has only opened the group chat twice, once at 9:00 and once at 22:00. Both times, she wrote down the list of members in the order they appeared at that time. Now she wonders: what is the minimum number of other members that must have been online at least once between 9:00 and 22:00?

Beppa is sure that no two members are ever online at the same time and no members are online when Beppa opens the group chat at 9:00 and 22:00.


-----Input-----

Each test contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 10000$) — the number of test cases. The descriptions of the $t$ test cases follow.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 10^5$) — the number of members of the group excluding Beppa.

The second line contains $n$ integers $a_1, \, a_2, \, \dots, \, a_n$ ($1 \le a_i \le n$) — the list of IDs of the members, sorted by decreasing times of last seen online at 9:00.

The third line contains $n$ integers $b_1, \, b_2, \, \dots, \, b_n$ ($1 \le b_i \le n$) — the list of IDs of the members, sorted by decreasing times of last seen online at 22:00.

For all $1\le i < j\le n$, it is guaranteed that $a_i \ne a_j$ and $b_i \ne b_j$.

It is also guaranteed that the sum of the values of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case, print the minimum number of members that must have been online between 9:00 and 22:00.


-----Examples-----

Input
4
5
1 4 2 5 3
4 5 1 2 3
6
1 2 3 4 5 6
1 2 3 4 5 6
8
8 2 4 7 1 6 5 3
5 6 1 4 8 2 7 3
1
1
1
Output
2
0
4
0


-----Note-----

In the first test case, members $4, 5$ must have been online between 9:00 and 22:00.

In the second test case, it is possible that nobody has been online between 9:00 and 22:00.

Source: codeforces | Difficulty: EASY
Tags: Amortized analysis


Solutions:
from sys import stdin, stdout
input = stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	p = q = n - 1
	c = 0
	while p >= 0:
		if a[p] == b[q]:
			q -= 1
		else:
			c += 1
		p -= 1
	print(c)


from collections import deque
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	A.reverse()
	A = deque(A)
	B = list(map(int, input().split()))
	result = 0
	i = n - 1
	for _ in range(len(A), 0, -1):
		q = A.popleft()
		if q == B[i]:
			result += 1
			i -= 1
		else:
			A.append(q)
	print(n - result)


import sys
input = sys.stdin.readline
cases = int(input())
for _ in range(cases):
	length = int(input())
	morning_ids = list(input().split())
	rank = {p: i for (i, p) in enumerate(morning_ids)}
	evening_ids = list(input().split())
	update_ranks = list(map(lambda x: rank[x], evening_ids))
	pre = float('inf')
	keep_num = 0
	for cur in reversed(update_ranks):
		if cur > pre:
			break
		keep_num += 1
		pre = cur
	print(length - keep_num)


def fun(n, a, b):
	(inda, indb) = (-1, -1)
	count = 0
	while inda >= -n:
		if a[inda] == b[indb]:
			count += 1
			indb -= 1
		inda -= 1
	return n - count
assert fun(5, [1, 4, 2, 5, 3], [4, 5, 1, 2, 3]) == 2
assert fun(6, [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6]) == 0
assert fun(8, [8, 2, 4, 7, 1, 6, 5, 3], [5, 6, 1, 4, 8, 2, 7, 3]) == 4
assert fun(8, [8, 2, 4, 7, 1, 6, 5, 3], [8, 6, 1, 4, 5, 2, 7, 3]) == 5
assert fun(8, [8, 2, 4, 7, 1, 6, 5, 3], [8, 6, 3, 4, 5, 2, 7, 1]) == 5
assert fun(8, [8, 2, 4, 7, 1, 6, 5, 3], [2, 8, 4, 7, 1, 6, 5, 3]) == 1
assert fun(1, [1], [1]) == 0
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print(fun(n, a, b))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = 0
	for i in range(n - 1, -1, -1):
		if a[i] != b[i + c]:
			c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	count = 0
	i = n - 1
	j = n - 1
	while i >= 0 and j >= 0:
		if arr1[i] == arr2[j]:
			i -= 1
			j -= 1
		else:
			count += 1
			i -= 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = 0
	j = 1
	for i in b[::-1]:
		while j <= n and a[-j] != i:
			j += 1
		if j > n:
			break
		else:
			ans += 1
	print(n - ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	ans = 0
	for i in range(n - 1, -1, -1):
		if arr[i] != brr[i + ans]:
			ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	arr1_d_pos = {}
	last_pos = n - 1
	ok = 0
	for x in range(n):
		arr1_d_pos[arr1[x]] = x
	for x in range(n - 1, -1, -1):
		curr = arr2[x]
		pos_in_arr1 = arr1_d_pos[curr]
		if pos_in_arr1 <= last_pos:
			last_pos = pos_in_arr1
			ok += 1
		else:
			break
	print(n - ok)


t = int(input())
for _ in range(t):
	input()
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	i = len(a) - 1
	j = len(a) - 1
	kont = 0
	while i >= 0:
		if a[i] == b[j]:
			i -= 1
			j -= 1
		else:
			kont += 1
			i -= 1
	print(kont)


from collections import defaultdict
for test in range(int(input())):
	n = int(input())
	indexx = {}
	online1 = list(map(int, input().split(' ')))
	for (ii, member) in enumerate(online1):
		indexx[member] = ii
	online2 = list(map(int, input().split(' ')))
	ans = online2.index(online1[0])
	i = ans + 1
	while i < n:
		prev = online2[i - 1]
		curr = online2[i]
		pos_prev_in_1 = indexx[prev]
		pos_curr_in_1 = indexx[curr]
		if pos_prev_in_1 > pos_curr_in_1:
			ans = i
		i += 1
	print(ans)


k = int(input())
for i in range(0, k):
	n = int(input())
	bl = list(map(int, input().split()))
	idi = list(map(int, input().split()))
	g = n - 1
	t = n - 1
	count = 0
	while t > -1:
		if idi[g] == bl[t]:
			count += 1
			g -= 1
		t -= 1
	print(n - count)


k = int(input())
res = []
while k > 0:
	memo = {}
	_ = input()
	x = input().split(' ')
	for i in range(len(x)):
		memo[int(x[i])] = i + 1
	x = input().split(' ')
	cur_seen = []
	for num in x:
		cur_seen.append(memo[int(num)])
	last_seen = [i for i in range(1, len(cur_seen) + 1)]
	left = 0
	cur = 0
	seen = set()
	q = 0
	for i in range(len(cur_seen)):
		if cur_seen[i] in seen:
			continue
		if last_seen[left] == cur_seen[i]:
			seen.add(cur_seen[i])
			q += 1
			while left < len(cur_seen):
				if last_seen[left] not in seen:
					break
				left += 1
		else:
			seen.add(cur_seen[i])
			cur += 1
			cur += q
			q = 0
	res.append(cur)
	k -= 1
for x in res:
	print(x)