依旧苹果树

题目描述

有 $n$ 棵苹果树围成一个圆圈。每棵树上都有一个苹果，第 $i$ 棵树上的苹果美丽值为 $b_i$，其中 $1 \le i \le n$。你开始站在第 1 棵树前。

在每棵树前，你可以选择吃掉该树上的苹果，或者跳过不吃。每做出选择后，你会移动到下一棵树：从第 $i$ 棵树前往第 $i+1$ 棵树（$1 \le i \le n-1$），从第 $n$ 棵树则回到第 1 棵树。你会这样不断循环地经过这些树。

但你有一个特别的限制：只有当当前苹果的美丽值严格大于你上一次吃掉的苹果的美丽值时，你才能吃下去。例如，若 $b = [2, 1, 2, 3]$，你若在第 1 棵树吃了苹果（美丽值 $2$），则不能吃第 2、3 棵树的苹果，因为它们的美丽值都不大于 $2$。但你可以在第 4 棵树吃下苹果，因为 $b_4 = 3 > 2$。

注意，每遇到一个苹果时你都可以选择先跳过不吃，之后某轮循环再次遇到时再选择是否吃掉。

你的任务是，若你每一步都做出最优决策，最多能吃到多少个苹果。

输入格式

每组测试包含多个测试用例。第一行包含整数 $t$（$1 \le t \le 500$），表示测试用例数。

每组测试用例第一行包含一个整数 $n$（$1 \le n \le 100$），表示苹果树数量。

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

注意，所有测试用例中 $n$ 的总和没有额外限制。

输出格式

对每个测试用例，输出一个整数，表示你最多可以吃到的苹果数量。

输入输出样例 #1

输入 #1

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

输出 #1

1
4
5

说明/提示

在第一个样例中，所有苹果的美丽值都相同，无论你先吃哪一个，之后都无法再吃其它任何苹果。因此最多只能吃 1 个。

在第二个样例中，你可以按照如下方式吃掉 4 个苹果：

• 在第 1 棵树前跳过。
• 在第 2 棵树前跳过。
• 在第 3 棵树前跳过。
• 在第 4 棵树吃掉苹果（美丽值 $1$）。
• 在第 5 棵树吃掉苹果（美丽值 $2$）。
• 在第 1 棵树前跳过。由于第 1 棵树的美丽值（$b_1=1$）不大于上次吃掉的苹果美丽值（$b_5=2$），因此不能吃。
• 在第 2 棵树吃掉苹果（美丽值 $4$）。
• 在第 3 棵树吃掉苹果（美丽值 $5$）。

可以证明你无法吃到 5 个苹果。因此最多只能吃 4 个。