A. Круг яблонь
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

По кругу расположено $$$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 \gt 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$$$ по всем наборам входных данных.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальное количество яблок, которые вы можете съесть.

Пример
Входные данные
3
4
2 2 2 2
5
1 4 5 1 2
6
5 4 2 1 2 3
Выходные данные
1
4
5
Примечание

В первом наборе входных данных, поскольку все яблоки имеют одинаковую красоту, независимо от того, какое яблоко вы съедите первым, вы не сможете съесть ни одно другое после этого. Следовательно, максимальное количество яблок, которые вы можете съесть, равно $$$1$$$.

Во втором наборе входных данных вы можете съесть четыре яблока следующим образом:

  • У дерева $$$1$$$ пропустите яблоко.
  • У дерева $$$2$$$ пропустите яблоко.
  • У дерева $$$3$$$ пропустите яблоко.
  • У дерева $$$4$$$ съешьте яблоко (красота $$$1$$$).
  • У дерева $$$5$$$ съешьте яблоко (красота $$$2$$$).
  • У дерева $$$1$$$ пропустите яблоко. Вы не можете его съесть, так как его красота ($$$b_1 = 1$$$) не больше красоты последнего съеденного вами яблока ($$$b_5 = 2$$$).
  • У дерева $$$2$$$ съешьте яблоко (красота $$$4$$$).
  • У дерева $$$3$$$ съешьте яблоко (красота $$$5$$$).

Можно доказать, что невозможно съесть все пять яблок; следовательно, максимальное количество яблок, которые вы можете съесть, равно $$$4$$$.