G. Another Shuffle
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Alexander bought himself a new deck of cards at a kiosk. The deck he bought contains $$$n$$$ cards, each of which has an integer from $$$0$$$ to $$$10^9$$$ written on it.

Alexander decided to shuffle the deck. Let $$$a_i$$$ be the value of the $$$i$$$-th card from the top of the deck. In one shuffle, Alexander performs the following actions:

  1. Splits the deck into one or more non-empty piles by cutting it between every pair of adjacent cards with equal values, that is, such that $$$a_i = a_{i+1}$$$;
  2. Stacks the piles in reverse order, preserving the order of cards inside each pile.

If there are no two adjacent cards with equal values in the deck, then when Alexander tries to shuffle it using his method, the order of cards in the deck does not change.

Alexander repeats shuffling until he encounters a card order that has already appeared before. He wonders how many shuffles he will perform before this happens. Help him answer this question.

Input

You need to solve the problem for one or more decks. The first line contains one integer $$$t$$$ — the number of decks Alexander has ($$$1 \le t \le 10^5$$$).

The descriptions of the $$$t$$$ decks follow. Each deck description consists of two lines.

The first line contains one integer $$$n$$$ — the number of cards ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ — the initial order of the cards from top to bottom ($$$0 \le a_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all decks in one test does not exceed $$$2 \cdot 10^5$$$.

Output

For each deck, output one integer — the minimum number of shuffles after which the order of cards in the deck coincides with one of the previously encountered orders.

Example
Input
3
5
0 1 1 2 2
5
0 1 2 1 0
4
1 2 2 1
Output
2
1
2
Note

In the first deck from the sample, the first shuffle will split it into piles $$$[0, 1]$$$, $$$[1, 2]$$$, $$$[2]$$$. After combining the piles in reverse order, the deck will look like $$$[2, 1, 2, 0, 1]$$$. Now it has no two adjacent equal cards, and after the second shuffle it will not change. In total, two shuffles are performed.

In the second deck, there are no adjacent equal cards from the start, so it will not change after the first shuffle.

After the first shuffle, the third deck becomes $$$[2, 1, 1, 2]$$$, and after the second one it becomes $$$[1, 2, 2, 1]$$$ and coincides with the initial deck.