Bir ülkede şehir ve her biri iki farklı şehri birbirine bağlayan n - 1 çift yönlü yol vardır. Yol ağı bağlantılıdır: herhangi bir şehirden herhangi bir başka şehre gidilebilir. Dolayısıyla herhangi iki şehir tam olarak bir rota ile birleşir; rota, hiçbir şehirden iki kez geçmeyen bir yoldur.
Her yolda negatif olmayan tam sayıda çukur vardır. Başkan, iki farklı şehir arasındaki her rotayı düzgün hâle getirmek istiyor. Bir rota, üzerindeki yolların çukur sayılarının bit düzeyinde AND'i bit düzeyinde OR'una eşitse düzgün olarak adlandırılır (bit düzeyindeki işlemler aşağıda hatırlatılmıştır).
Bir yol ekibi aşağıdaki işlemi istediği kadar tekrarlayabilir:
Farklı iki şehir ve ile bir tam sayı i \ge 0 seçmek ve 'dan 'ye giden rotanın her yolunda çukur sayısı 'yi w \oplus 2^i ile değiştirmek (yani numaralı biti tersine çevirmek).
Tanımları hatırlayalım. Negatif olmayan bir tam sayının numaralı biti, onun 2^i konumundaki ikilik basamağıdır ( numaralı bit en düşük anlamlı bittir).
Birkaç tam sayının bit düzeyinde AND'inde numaralı bit, ancak ve ancak bu sayıların hepsinde numaralı bit ise olur.
Birkaç tam sayının bit düzeyinde OR'unda numaralı bit, ancak ve ancak bu sayıların en az birinde numaralı bit ise olur.
İki tam sayının bit düzeyinde XOR'unda () numaralı bit, ancak ve ancak bu iki sayıda numaralı bitler farklıysa olur. Özellikle w \oplus 2^i, sayısının numaralı biti tersine çevrilmiş hâlidir.
İki farklı şehir arasındaki her rotayı düzgün hâle getirmek için gereken en az işlem sayısını bulun.
İlk satırda bir tam sayı (1 \le t \le 10^5) — test durumlarının sayısı verilir.
Her test durumunun ilk satırında bir tam sayı (1 \le n \le 2 \cdot 10^5) — şehirlerin sayısı verilir. Sonraki n - 1 satırın her biri üç tam sayı , ve (1 \le u, v \le n, u \ne v, 0 \le w < 2^{30}) içerir: ve şehirleri arasında çukuru olan bir yol. Yol ağının bağlantılı olduğu garanti edilir.
Tüm test durumları üzerinden değerlerinin toplamı 2 \cdot 10^5'i aşmaz.
Her test durumu için bir tam sayı — en az işlem sayısını yazdırın.
Örnek 1
Birinci test durumunda şehirler 1 - 2 - 3 - 4 - 5 zincirini oluşturur ve yollarında 1, 0, 0, 1 çukur vardır. Bir işlem yeterlidir: numaralı şehirden numaralı şehre giden rotada numaralı biti tersine çevirmek. O zaman her yolda çukur olur.
İkinci test durumunda numaralı şehirden numaralı şehre giden rotada i = 2 ile yapılan bir işlem sayısını yapar ve dört yolun hepsinde çukur olur.
Üçüncü test durumunda yalnızca bir şehir vardır, bu yüzden farklı şehirler arasında rota yoktur ve hiçbir şey yapmaya gerek yoktur.
Dördüncü test durumunda 1 - 2 - 3 - 4 zincirinde çukur vardır. Üç işlem yeterlidir: i = 0 ile 1 \to 3 rotası, i = 1 ile 2 \to 3 rotası ve i = 2 ile 1 \to 2 rotası. O zaman her yolda çukur olur.
Beşinci test durumunda numaralı şehir , ve numaralı şehirlere bağlıdır ve 2 - 3, 4 - 5 ile 6 - 7 yolları üç dalı devam ettirir. numaralı şehirden çıkan üç yolda çukur, dıştaki üç yolda ise çukur vardır. İki işlem yeterlidir: i = 0 ile 2 \to 4 rotası ve i = 0 ile 1 \to 6 rotası. O zaman her yolda çukur olur. Bir işlemin yeterli olmadığı gösterilebilir.