Subodh

Subodh is going to paint a very big wall. The wall is composed of $N$ adjacent parts in line. He wants to paint each part with a particular color. He paints in a somewhat peculiar mechanism. At each step he chooses some consecutive parts of the wall and paints them with same color. Initially, there is no color on any part of the wall. You’re given the target color for each part of the wall. You have to tell the minimum number of steps Subodh will require if he wants to paint the whole wall in the desired color combination using his peculiar approach.

Input

First line of input will contain $T$ ($0 < T \le 60$), the number of test cases. First line of each test case will contain $N$ ($0 < N \le 200$) number of parts in the wall and then follows N numbers on the next line. The $i$-th ($1 \le i \le N$) number $C_i$ ($1 \le C_i \le N$) represents the required color on the $i$-th part of the wall.

Output

For each test case provide the minimum number of required steps.

Sample

Input	Output
2 5 1 1 2 2 2 3 1 2 1	2 2
For the first case, he can choose the first two parts in step one and paint them with color 1 and in second step, choose the remaining three parts and paint them with color 2. For the second case, he can paint the whole wall with color 1 in first step and then paint second part with color 2 in second step.