Minimum Colors to Paint Buildings

Given a sequence of buildings, each with a certain height, determine the minimum number of colors needed to paint all the buildings such that no two adjacent buildings (when their heights differ) are painted with the same color.

In other words, if all consecutive buildings have the same height, you can paint them all with a single color; otherwise, at least two colors are required.

The answer for each test case is either $1$ or $2$.

inputFormat

The input is read from standard input (stdin). The first line contains an integer $T$, the number of test cases. Each test case consists of two lines. The first line contains an integer $n$, representing the number of buildings. The second line contains $n$ space-separated integers, where the $i$-th integer denotes the height of the $i$-th building.

outputFormat

For each test case, output the minimum number of colors required on a new line. The output should be printed to standard output (stdout).## sample

3
3
1 2 3
4
10 10 10 10
5
5 4 5 4 5

2
1
2