Algorithmen Übungen WS13/14

Every year in september the Einstein-Marathon in Ulm takes place. At the beginning of the race the participants should line up at the start area in accordance with their expected finish time. It's clear that this will make everyone's life easier. There's nothing more frustrating for the quicker runners to be dodging other people at the start and nothing more demoralising for the slower runners than being overtaken by hundreds of quicker runners. Unfortunately there are always people who overestimate their performance by far and start in front of the field. So many overtakings will happen during the race. The organizers of the marathon want to know how many overtakings have at least happend during the race and ask you for help. They have a file which lists the starting number of each runner according to the time they crossed the starting line. A second is ordered according the time they crossed the finishing line.

Input

The first line contains the number of marathons t (t<100). Each marathon is specified by three lines. The first line contains the number of runners n (1<n≤40000). The second line is a permutation of the starting numbers 1,...,n which represents the order in which the runners passed the starting line. Finally the third line a permutation which represents the finishing order.

Output

For each marathon output one line which contains the minimal number of overtakings that have happend during the race. See the sample output for the detailed format.

Example

Input:
3
5
1 2 4 3 5 
1 2 3 4 5 
6
2 3 4 5 6 1 
1 2 3 4 5 6 
7
7 6 5 4 3 2 1 
1 2 3 4 5 6 7 


Output:
at least 1 overtaking(s)
at least 5 overtaking(s)
at least 21 overtaking(s)