Вы - учитель в новом детском саду "Маленькие кодеры". В Вашем классе имеется n детей, у каждого из них имеется уникальный идентификационный номер ученика (от 1 до n). Каждый ребенок в классе имеет единственного лучшего друга, и Вы знаете этого лучшего друга для каждого ребенка. Отношение дружбы не всегда взаимно, то есть если B лучший друг А, то это не значит что A лучший друг B.
Ваш завтрашний план урока включает в себя мероприятие, в котором участники должны сидеть в кругу. Вы хотите сделать мероприятие настолько успешным, насколько это возможно, создав максимально возможный круг детей, чтобы каждый ребенок в круге сидел прямо рядом со своим наилучшим другом либо слева, либо справа. Любые дети, не входящие в круг, будут наблюдать за мероприятием, не участвуя в нем.
Какое наибольшее количество детей может быть в кругу?
Первая строка содержит количество тестов t (1 ≤ t ≤ 100). Далее следуют t тестов. Каждый тест состоит из двух строк. Первая строка содержит число n (3 ≤ n ≤ 1000) - общее количество детей в классе. Вторая строка содержит n целых чисел F[1]
, F[2]
, ..., F[n]
, где F[i]
(1 ≤ F[i]
≤ n) - ID номер школьника, являющегося наилучшим другом школьника с ID номером i.
Для каждого теста выведите одну строку "Case #x: y", где x - номер теста (начиная с 1) и y - наибольшее количество детей, которое можно расположить по кругу так чтобы каждый ребенок в кругу располагался возле своего наилучшего друга.