## Compress the Video solution codechef

Chef recorded a video explaining his favorite recipe. However, the size of the video is too large to upload on the internet. He wants to compress the video so that it has the minimum size possible.

Chef’s video has NN frames initially. The value of the ithith frame is AiAi. Chef can do the following type of operation:

- Choose an index ii (1≤i≤N)(1≤i≤N) such that the value of the ithith frame is
**equal**to the value of**either**of its neighbors and**remove**the ithith frame.

Find the **minimum** number of frames Chef can achieve.

### Input Format

## Compress the Video solution codechef

- First line will contain TT, the number of test cases. Then the test cases follow.
- The first line of each test case contains a single integer NN – the number of frames initially.
- The second line contains NN space-separated integers, A1,A2,…,ANA1,A2,…,AN – the values of the frames.

### Output Format

For each test case, output in a single line the **minimum** number of frames Chef can achieve.

### Constraints

## Compress the Video solution codechef

- 1≤T≤10001≤T≤1000
- 1≤N≤1051≤N≤105
- 1≤Ai≤1061≤Ai≤106
- Sum of NN over all test cases does not exceed 2⋅1052⋅105.

### Sample Input 1

```
4
1
5
2
1 1
3
1 2 3
4
2 1 2 2
```

### Sample Output 1

## Compress the Video solution codechef

```
1
1
3
3
```

### Explanation

## Compress the Video solution codechef

**Test case 11:** There is only one frame with value 55. Since there are no neighbors, Chef won’t remove any frame and the minimum number of frames Chef can achieve is 11.

CodeChef was created as a platform to help programmers make it big in the world of algorithms, computer programming and programming contests. At CodeChef, we work hard to revive the geek in you by hosting a programming contest at the start of the month and another smaller programming challenge in the middle of the month.

**Test case 22:** There are two frames where both frames have value 11. Chef can remove the first frame as the value of the first frame is equal to that of the second frame. The remaining frames have values [1][1]. The minimum number of frames Chef can achieve is 11.

**Test case 33:** There are 33 frames. All frames have distinct values. Thus, the minimum number of frames Chef can achieve is 33.

**Test case 44:** Chef can remove the fourth frame as the value of the fourth frame is equal to that of the third frame. The remaining frames have values [2,1,2][2,1,2]. Thus, the minimum number of frames Chef can achieve is 33.