Longest Valid Subsequence

Given a sequence of flower heights, your task is to determine the length of the longest valid subsequence where no two consecutive flowers have the same height.

A valid subsequence is defined as a sequence that can be derived from the original sequence by removing some or no elements without changing the order of the remaining elements, such that for every adjacent pair in the subsequence, the heights are different.

You can refer to the formula below for clarification:

$$ ans = 1 + \sum_{i=1}^{N-1} [h[i] \neq h[i-1]] $$

Here, \(h[i]\) denotes the height of the \(i^{th}\) flower and \([\cdot]\) is the Iverson bracket which is 1 if the condition inside is true and 0 otherwise.

inputFormat

The input is given via standard input (stdin). The first line contains an integer \(T\) representing the number of test cases. Each test case consists of two lines:

• The first line contains a single integer \(N\), the number of flowers.
• The second line contains \(N\) space-separated integers representing the heights of the flowers.

outputFormat

For each test case, output a single line containing the length of the longest valid subsequence where no two adjacent flowers have the same height.

## sample

2
5
1 2 2 3 4
6
5 6 5 5 7 8

4
5

</p>