Sizə -dən -ə qədər nömrələnmiş təpəsi olan ağac verilir. İki təpə arasındakı məsafə onların arasındakı sadə yoldakı tillərin sayıdır.
Boş olmayan təpələr çoxluğu əlaqəli adlanır, əgər -in istənilən iki təpəsi üçün onların arasındakı sadə yolun bütün təpələri də -ə aiddirsə.
-dən -ə qədər hər bir üçün elə əlaqəli çoxluğunun maksimal ölçüsünü tapın ki, -in istənilən iki təpəsi arasındakı məsafə -dən böyük olmasın.
Birinci sətirdə bir tam ədəd (1 \le t \le 5000) — test hallarının sayı verilir.
Hər test halının birinci sətrində tam ədəd (1 \le n \le 5000) — təpələrin sayı verilir. Növbəti n - 1 sətrin hər birində iki tam ədəd və (1 \le u, v \le n, u \ne v) — və təpələri arasındakı til verilir. Tillərin ağac əmələ gətirdiyi qarantiya olunur.
Bütün test halları üzrə qiymətlərinin cəmi -i aşmır.
Hər test halı üçün tam ədəddən ibarət bir sətir çap edin: onlardan -incisi elə əlaqəli təpələr çoxluğunun maksimal ölçüsü olmalıdır ki, orada istənilən iki təpə arasındakı məsafə -dən böyük olmasın.
Nümunə 1
Birinci test halında ağacın təpəsi var: təpəsi , və ilə qonşudur, təpəsi isə , və ilə qonşudur.
x = 1 üçün cavab -dir, məsələn S = \{1, 3\}.
x = 2 üçün cavab -dür, məsələn S = \{1, 3, 4, 5\}.
x = 3 üçün cavab -dir, məsələn S = \{1, 3, 4, 5, 7\}: ən böyük məsafələr ilə arasında və ilə arasındadır və onlar -ə bərabərdir.
x \ge 4 üçün cavab -dir, çünki bütün təpələr çoxluğunun ən böyük məsafəsi -dür.
İkinci test halında ağac yalnız bir təpədən ibarətdir, buna görə cavab -dir.
Üçüncü test halında ağac 1 - 2 - 3 - 4 zənciridir. Zəncirin təpədən ibarət əlaqəli çoxluğunun ən böyük məsafəsi k - 1-dir, buna görə x = 1, 2, 3, 4 üçün cavablar 2, 3, 4, 4-dür.