苹果树环

有 n 棵苹果树排成一个环。每棵树上恰好结一个苹果，第 i 棵树上苹果的美观度用 bi 表示（1≤i≤n）。你从第 1 棵树前开始行动。

在每棵树前，你可以选择吃掉苹果或跳过苹果。做出选择后，你会移动到下一棵树：对于 1≤i≤n-1，从第 i 棵树移动到第 i+1 棵树；从第 n 棵树移动则会回到第 1 棵树。你会如此循环移动，无限重复这个过程。

不过，你需要遵守一个特殊规则：只有当当前苹果的美观度严格大于你上一个吃掉的苹果的美观度时，你才能吃掉当前这个苹果。 例如，若美观度数组 b=[2,1,2,3]，且你吃掉了第 1 棵树的苹果（美观度 2），那么你不能吃掉第 2 棵和第 3 棵树的苹果（因为它们的美观度不大于 2）；但你可以吃掉第 4 棵树的苹果，因为 b4=3>2。

请注意，你第一次遇到某棵树时可以选择跳过苹果，之后在后续循环中再次遇到这棵树时，仍可以选择吃掉它。

你的任务是：通过对 “何时吃苹果、何时跳过苹果” 做出最优决策，求出你最多能吃掉的苹果数量。

输入

输入包含多组测试用例。第一行输入一个整数 t，表示测试用例的数量。接下来依次描述每组测试用例：

• 每组测试用例的第一行包含一个整数 n，表示苹果树的数量。

• 每组测试用例的第二行包含 n 个整数 b₁,b₂,…,bₙ，表示每棵树上苹果的美观度。

请注意，题目对所有测试用例的 n 之和没有额外限制。

输出

对于每组测试用例，输出一个整数，代表你最多能吃掉的苹果数量。

示例

输入

3

4

2 2 2 2

5

1 4 5 1 2

6

5 4 2 1 2 3

输出

1
4
5

数据范围

1≤t≤500，1≤n≤100，1≤bi≤n