• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

تعداد $n$ مکتب در شهر استاد وجود دارد. هر مکتب تعدادی عضو دارد و هر عضو مکتب به جز عضو اول آن که پیر نامیده می‌شود، یکی دیگر از اعضا را به عنوان مراد خود انتخاب کرده‌است. این انتخاب‌ها به گونه‌ای انجام شده‌اند که ساختار هر مکتب، مشابه یک درخت ریشه‌دار است.

در راستای هم‌افزایی مکاتب، استاد اقدام به ادغام مکاتب برای تشکیل یک مکتب واحد کرده‌است. او تا زمانی که حداقل دو مکتب وجود دارد، با قرار دادن یک نفر به عنوان مراد پیر مکتب دیگر، آن دو مکتب را ادغام کرده و آن پیر را به مرید تغییر می‌دهد. توجه کنید که با این حساب در نهایت یک مکتب باقی ‌می‌ماند که ساختار آن همانند یک درخت ریشه‌دار است.

قطر درخت مکتب نهایی به عنوان میزان همبستگی شناخته می‌شود. بیشینه‌ی قطر ممکن را بیابید.

ورودی

در خط اول ورودی عدد صحیح $t$ که برابر تعداد سناریوها است، می‌آید. $$1 \le t \le 100,000$$

در خط اول هر سناریو، عدد صحیح $n$ که برابر تعداد مکاتب در آن سناریو است، می‌آید.

$$1 \le n \le 1,000,000$$

سپس اطلاعات مکتب‌ها داده می‌شوند. برای هر مکتب ابتدا در یک خط عدد صحیح $m$ که برابر تعداد افراد عضو آن مکتب است می‌آید.

$$1 \le m \le 1,000,000$$

سپس در خط بعدی، $m-1$ عدد $p_2, p_3, \dots, p_m,$ می‌آیند که نشان می‌دهند مراد فرد $i$-ام مکتب، فرد $p_i$-ام است. فرد اول مکتب، پیر و ریشه‌ی مکتب است (توجه کنید چناچه مکتب تنها یک عضو داشته باشد این خط خالی خواهد بود).

$$1 \le p_i < i$$

تضمین می‌شود مجموع تعداد اعضای مکاتب در همه‌ی سناریوها حداکثر برابر $1,000,000$ است.

خروجی

برای هر سناریو، در یک خط، بیشینه‌ی همبستگی را خروجی دهید.

مثال

ورودی نمونه ۱

2
2
4
1 2 3
6
1 2 1 3 4
3
4
1 2 2
3
1 1
3
1 2

خروجی نمونه ۱

9
8