Найкращі друзі#8516

Найкращі друзі

1 секунда

128 мегабайтів

Легка

Ви - вчитель у новому дитячому садку "Маленькі кодери". У вашому класі є $n$ дітей, кожен з яких має унікальний ідентифікаційний номер учня (від $1$ до $n$ ). Кожна дитина має одного найкращого друга, і ви знаєте, хто це для кожної дитини. Відносини дружби не завжди взаємні, тобто якщо B є найкращим другом A, це не означає, що A є найкращим другом B.

Ваш план уроку на завтра включає захід, під час якого учасники повинні сидіти в колі. Ви хочете зробити захід максимально успішним, створивши найбільше можливе коло дітей, щоб кожна дитина в колі сиділа поруч зі своїм найкращим другом, зліва або справа. Діти, які не увійдуть до кола, будуть спостерігати за заходом, не беручи в ньому участь.

Яка найбільша кількість дітей може бути в колі?

Вхідні дані

Перший рядок містить кількість тестів $t$ ( $1 \leq t \leq 100$ 1 \le t \le 100). Далі йдуть $t$ тестів. Кожен тест складається з двох рядків. Перший рядок містить число $n$ ( $3 \leq n \leq 1000$ 3 \le n \le 1000) - загальна кількість дітей у класі. Другий рядок містить $n$ цілих чисел $F_{1}, F_{2}, \dots, F_{n}$ F_1, F_2, \ldots, F_n, де $F_{i}$ F_i ( $1 \leq F_{i} \leq n$ 1 \le F_i \le n) - ID номер школяра, який є найкращим другом школяра з ID номером $i$ .

Вихідні дані

Для кожного тесту виведіть один рядок "Case #x: y", де $x$ - номер тесту (починаючи з $1$ ) і $y$ - найбільша кількість дітей, яку можна розташувати по колу так, щоб кожна дитина в колі розташовувалася біля свого найкращого друга.

Приклади

Приклад 1