Ən yaxşı dostlar

Siz "Kiçik Kodlayıcılar" adlı yeni uşaq bağçasında müəllimsiniz. Sinifinizdə hər birinin unikal şagird identifikasiya nömrəsi olan n uşaq var (bu nömrələr 1-dən n-ə qədərdir). Sinifdəki hər bir uşağın yalnız bir ən yaxşı dostu var və siz hər bir uşağın ən yaxşı dostunu bilirsiniz. Dostluq münasibəti həmişə qarşılıqlı olmur, yəni əgər B A-nın ən yaxşı dostudursa, bu, A-nın da B-nin ən yaxşı dostu olduğu anlamına gəlmir.

Sabahkı dərs planınıza dair bir tədbir var ki, iştirakçılar dairə şəklində oturmalıdırlar. Tədbiri mümkün qədər uğurlu etmək istəyirsiniz, yəni uşaqları elə bir dairə şəklində yerləşdirmək istəyirsiniz ki, dairədəki hər bir uşaq öz ən yaxşı dostunun ya solunda, ya da sağında otursun. Dairəyə daxil olmayan uşaqlar tədbiri izləyəcək, lakin iştirak etməyəcəklər.

Dairədə ola biləcək maksimum uşaq sayını tapın.

Giriş məlumatları

Birinci sətir testlərin sayını t (1 ≤ t ≤ 100) ehtiva edir. Sonra t test gəlir. Hər bir test iki sətirdən ibarətdir. Birinci sətir sinifdəki ümumi uşaq sayını n (3 ≤ n ≤ 1000) ehtiva edir. İkinci sətir F[1], F[2], ..., F[n] tam ədədlərini ehtiva edir, burada F[i] (1 ≤ F[i] ≤ n) - ID nömrəsi i olan şagirdin ən yaxşı dostunun ID nömrəsidir.

Çıxış məlumatları

Hər bir test üçün "Case #x: y" şəklində bir sətir çıxarın, burada x testin nömrəsidir (başlayaraq 1-dən) və y dairədə yerləşdirilə biləcək maksimum uşaq sayıdır ki, dairədəki hər bir uşaq öz ən yaxşı dostunun yanında otursun.