Bir ölkədə şəhər və hər biri iki müxtəlif şəhəri birləşdirən n - 1 ikitərəfli yol var. Yol şəbəkəsi əlaqəlidir: istənilən şəhərdən istənilən başqa şəhərə getmək olar. Deməli, istənilən iki şəhəri dəqiq bir marşrut birləşdirir — heç bir şəhərdən iki dəfə keçməyən yol.
Hər yolda mənfi olmayan tam sayda çuxur var. Prezident iki müxtəlif şəhər arasındakı hər marşrutu hamar etmək istəyir. Marşrut hamar adlanır, əgər onun yollarındakı çuxur saylarının bit üzrə AND-i onların bit üzrə OR-una bərabərdirsə (bit əməlləri aşağıda xatırladılır).
Yol briqadası aşağıdakı əməliyyatı istənilən sayda təkrarlaya bilər:
İki müxtəlif və şəhərini və i \ge 0 tam ədədini seçmək və -dan -yə gedən marşrutun hər yolunda çuxurların sayı -ni w \oplus 2^i ilə əvəz etmək (yəni nömrəli biti əksinə dəyişmək).
Tərifləri xatırladaq. Mənfi olmayan tam ədədin nömrəli biti onun 2^i mövqeyindəki ikilik rəqəmidir ( nömrəli bit ən kiçik mərtəbəlidir).
Bir neçə tam ədədin bit üzrə AND-ində nömrəli bit yalnız və yalnız o halda -ə bərabərdir ki, nömrəli bit onların hər birində -ə bərabər olsun.
Bir neçə tam ədədin bit üzrə OR-unda nömrəli bit yalnız və yalnız o halda -ə bərabərdir ki, nömrəli bit onların heç olmasa birində -ə bərabər olsun.
İki tam ədədin bit üzrə XOR-unda () nömrəli bit yalnız və yalnız o halda -ə bərabərdir ki, bu iki ədəddə nömrəli bitlər fərqli olsun. Xüsusən, w \oplus 2^i — bu, nömrəli biti əksinə dəyişilmiş ədədidir.
İki müxtəlif şəhər arasındakı hər marşrutu hamar etmək üçün lazım olan minimum əməliyyat sayını tapın.
Birinci sətirdə bir tam ədəd (1 \le t \le 10^5) — test hallarının sayı verilir.
Hər test halının birinci sətrində bir tam ədəd (1 \le n \le 2 \cdot 10^5) — şəhərlərin sayı verilir. Sonrakı n - 1 sətrin hər biri üç tam ədəd , və (1 \le u, v \le n, u \ne v, 0 \le w < 2^{30}) ehtiva edir: və şəhərləri arasında çuxuru olan yol. Yol şəbəkəsinin əlaqəli olduğu təmin edilir.
Bütün test halları üzrə -lərin cəmi 2 \cdot 10^5-i aşmır.
Hər test halı üçün bir tam ədəd — minimum əməliyyat sayını çap edin.
Nümunə 1
Birinci test halında şəhərlər 1 - 2 - 3 - 4 - 5 zənciri əmələ gətirir və onun yollarında 1, 0, 0, 1 çuxur var. Bir əməliyyat kifayətdir: nömrəli şəhərdən nömrəli şəhərə gedən marşrutda nömrəli biti əksinə dəyişmək. Onda hər yolda çuxur olar.
İkinci test halında nömrəli şəhərdən nömrəli şəhərə gedən marşrutda i = 2 ilə bir əməliyyat -ni -ya çevirir və hər dörd yolda çuxur olur.
Üçüncü test halında yalnız bir şəhər var, ona görə də müxtəlif şəhərlər arasında marşrut yoxdur və heç nə etmək lazım deyil.
Dördüncü test halında 1 - 2 - 3 - 4 zəncirinin yollarında çuxur var. Üç əməliyyat kifayətdir: i = 0 ilə 1 \to 3 marşrutu, i = 1 ilə 2 \to 3 marşrutu və i = 2 ilə 1 \to 2 marşrutu. Onda hər yolda çuxur olar.
Beşinci test halında nömrəli şəhər , və şəhərləri ilə birləşir, 2 - 3, 4 - 5 və 6 - 7 yolları isə üç budağı davam etdirir. nömrəli şəhərdən çıxan üç yolda çuxur, kənar üç yolda isə çuxur var. İki əməliyyat kifayətdir: i = 0 ilə 2 \to 4 marşrutu və i = 0 ilə 1 \to 6 marşrutu. Onda hər yolda çuxur olar. Göstərmək olar ki, bir əməliyyat kifayət deyil.