题目描述

有 $n$ 棵苹果树按环形排列。每棵树恰好结一个苹果，第 $i$ 棵树上的苹果美丽值为 $b_i\ (1\le i\le n)$。你从第 $1$ 棵树前开始。

你在每棵树处可以选择吃掉该树的苹果或跳过该苹果。做出选择后你会移动到下一棵树：对 $1\le i\le n-1$，从第 $i$ 棵移到第 $i+1$ 棵；从第 $n$ 棵则回到第 $1$ 棵。你会无限次按此顺序循环经过这些树。

但有一个限制：你只能在苹果的美丽值 严格大于 上一次吃到的苹果的美丽值时吃该苹果。比如 $b=[2,1,2,3]$，若你在第 $1$ 棵吃了苹果（美丽值 $2$），那么第 $2$、第 $3$ 棵的苹果都不能吃（$1,2\not>2$），但第 $4$ 棵的苹果可以吃（$3>2$）。

注意：你可以在首次遇到某个苹果时选择跳过，稍后在后续循环中再决定是否吃该苹果。

请你在所有策略中选择最优策略，计算你最多能吃到多少个苹果。

输入格式

第一行包含一个整数 $t$（$1\le t\le 500$），表示测试用例个数。接下来描述 $t$ 个测试用例。

每个测试用例包含两行：

• 第一行包含一个整数 $n$（$1\le n\le 100$），表示苹果树的数量。
• 第二行包含 $n$ 个整数 $b_1,b_2,\dots,b_n$（$1\le b_i\le n$），表示每棵树上苹果的美丽值。

输出格式

对每个测试用例，输出一行，包含一个整数——你最多能吃到的苹果数量。

样例输入

3
4
2 2 2 2
5
1 4 5 1 2
6
5 4 2 1 2 3

样例输出

1
4
5

说明

样例解释

• 在第一个测试用例中，所有苹果美丽值相同，无论先吃哪个，之后都不能再吃其它，因此最多吃 $1$ 个。
• 在第二个测试用例中，一个可行且最优的操作序列为：在第 $4$ 棵吃（美丽 $1$）、第 $5$ 棵吃（美丽 $2$）、随后在下一轮第 $2$ 棵吃（美丽 $4$）、第 $3$ 棵吃（美丽 $5$），共吃 $4$ 个苹果。可以证明无法吃到全部 $5$ 个。