Minimum Operations to Transform an Array

You are given two arrays of strings A and B, each containing n distinct elements. Array B is a permutation of A. Your task is to transform array A into array B using the minimum number of operations.

In one operation, you can choose any element from A and move it to any other position within A. The goal is to achieve the order specified by B using as few moves as possible.

This problem can be solved by recognizing that the minimum number of operations (\(\text{min\_ops}\)) is equal to the total number of elements n minus the length of the longest increasing subsequence (LIS) of A when its elements are replaced by their corresponding indices in B. That is:

[ \text{min_ops} = n - |\text{LIS}| ]

For example, if A = ["apple", "banana", "cherry"] and B = ["banana", "apple", "cherry"], by mapping each element of A to its index in B (i.e. "apple" \(\to 1\), "banana" \(\to 0\), "cherry" \(\to 2\)), you can compute the longest increasing subsequence and hence the minimum moves.

inputFormat

The input is given from standard input (stdin) and has the following format:

The first line contains an integer T, the number of test cases.

For each test case:

• The first line contains an integer n, the number of elements in the arrays.
• The second line contains n space-separated strings representing the initial array A.
• The third line contains n space-separated strings representing the target array B.

It is guaranteed that array B is a permutation of array A.

outputFormat

For each test case, output a single integer on a new line representing the minimum number of operations required to transform array A into array B.## sample

2
3
apple banana cherry
banana apple cherry
4
dog cat mouse bird
bird mouse cat dog

1
3