A. Два друга
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп хочет устроить вечеринку. У него есть $$$n$$$ друзей, и он хочет, чтобы на его вечеринке было как минимум $$$2$$$ из них.

Лучший друг $$$i$$$-го друга — это $$$p_i$$$. Все $$$p_i$$$ различны, и для каждого $$$i \in [1, n]$$$, $$$p_i \ne i$$$.

Монокарп может отправлять приглашения друзьям. $$$i$$$-й друг придет на вечеринку, если приглашение получат и друг $$$i$$$, и друг $$$p_i$$$ (обратите внимание, что друг $$$p_i$$$ не обязан прийти на вечеринку). Каждое приглашение отправляется ровно одному другу.

Например, если $$$p = [3, 1, 2, 5, 4]$$$, и Монокарп отправляет приглашения друзьям $$$[1, 2, 4, 5]$$$, то на вечеринку придут друзья $$$[2, 4, 5]$$$. Друг $$$1$$$ не придет, так как его лучший друг не получил приглашение; друг $$$3$$$ не придет, так как он не получил приглашение.

Вычислите минимальное количество приглашений, которые Монокарп должен отправить, чтобы как минимум $$$2$$$ друга пришли на вечеринку.

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из двух строк:

  • в первой строке записано одно целое число $$$n$$$ ($$$2 \le n \le 50$$$) — количество друзей;
  • во второй строке записаны $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$; $$$p_i \ne i$$$; все $$$p_i$$$ различны).
Выходные данные

Выведите одно целое число — минимальное количество приглашений, которые Монокарп должен отправить.

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

В первом наборе входных данных Монокарп может отправить приглашения друзьям $$$4$$$ и $$$5$$$. Оба придут на вечеринку, так как они лучшие друзья друг друга, и у каждого из них есть приглашение.

Во втором наборе Монокарп может отправить приглашения друзьям $$$1, 2$$$ и $$$3$$$, например. Тогда придут друзья $$$1$$$ и $$$2$$$: у друга $$$1$$$ и его лучшего друга $$$2$$$ есть приглашения, у друга $$$2$$$ и его лучшего друга $$$3$$$ есть приглашения. Друг $$$3$$$ не придет, так как его лучший друг $$$4$$$ не имеет приглашения. Невозможно отправить приглашения меньше чем $$$3$$$ друзьям таким образом, чтобы пришло хотя бы $$$2$$$.

В третьем наборе Монокарп может отправить приглашения обоим друзьям $$$1$$$ и $$$2$$$, и оба придут.