Top 25 Poll Comparison

Interview

Time limit10sMemory limit256 MB

Summary

Split two rankings of the same teams into the smallest consecutive groups that hold the same teams and print each size.

Level: Medium5 of 10
Topics: Greedy, Hash map
Solved: No attempts yet

Problem

In college football, many different sources publish their own list of the top 25 teams in the country. Ranking is subjective, so these lists differ, but they are usually close. Compare two such lists and find how far they agree.

Split the positions of the two lists into consecutive groups. Each group covers the same range of positions in both lists and holds the same set of teams in both lists. Make the groups as small as possible under that rule. If the two lists are identical, there are $N$ groups.

Take these two lists.

K&R Poll	Lovelace Ranking
A	A
B	C
C	D
D	B
E	E

There are 3 groups.

  A
B C D
  E

Input

The first line contains the number of test cases $T$ , where $1 \le T \le 100$ .

The first line of each test case contains the number of ranked teams $N$ , where $1 \le N \le 10^6$ . The next $N$ lines hold the first list in ranked order, one team per line. The following $N$ lines hold the second list in the same format.

A team name consists of at most 8 capital letters. Both lists contain the same team names, and within one test case all $N$ names are distinct.

Output

For each test case, print the size of each group in order on one line, separated by single spaces. Print no extra spaces and no blank lines between the numbers.

Examples7

Example 1

Input

3
5
A
B
C
D
E
A
C
D
B
E
3
RED
BLUE
ORANGE
RED
BLUE
ORANGE
3
MOE
LARRY
CURLY
CURLY
MOE
LARRY

Expected output

1 3 1
1 1 1
3

Example 2
Input
```
1
1
A
A
```
Expected output
```
1
```

Example 3

Input

1
6
ALPHA
BRAVO
CHARLIE
DELTA
ECHO
FOXTROT
ALPHA
BRAVO
CHARLIE
DELTA
ECHO
FOXTROT

Expected output

1 1 1 1 1 1

Example 4

Input

1
5
ALPHA
BRAVO
CHARLIE
DELTA
ECHO
ECHO
DELTA
CHARLIE
BRAVO
ALPHA

Expected output

Example 5
Input
```
1
6
A
B
C
D
E
F
B
A
D
C
F
E
```
Expected output
```
2 2 2
```

Example 6

Input

1
4
ABCDEFGH
IJKLMNOP
QRSTUVWX
YZABCDEF
ABCDEFGH
QRSTUVWX
IJKLMNOP
YZABCDEF

Expected output

1 2 1

Example 7

Input

4
2
X
Y
Y
X
4
ONE
TWO
THREE
FOUR
ONE
TWO
THREE
FOUR
5
P
Q
R
S
T
Q
R
P
T
S
1
SOLO
SOLO

Expected output