Mənfi olmayan tam ədədinin ikilik yazılışındakı vahid bitlərin sayını ilə işarə edək.
təpəli ağac və tam ədədi verilib. Hər bir təpəsi üçün aşağıdakı məsələni nəzərdən keçirin.
təpəsi ağacın köküdür. Ona 2^m-1 ədədi, digər hər bir təpəyə isə -dən 2^m-1-ə qədər tam ədəd mənimsədilir. kökdən təpəsinə gedən yoldakı ədədlərin, yolun hər iki ucu daxil olmaqla, bitlər üzrə AND-i olsun.
Bütün kökdən fərqli təpələri üçün \operatorname{popcount}(\operatorname{AND}(v)) eynidirsə, yerləşdirmə cəlbedici adlanır. Hər bir mümkün kök üçün cəlbedici yerləşdirmələrin sayını moduluna görə tapın.
n=1 olduqda yeganə yerləşdirmə cəlbedici hesab olunur.
Birinci sətirdə testlərin sayını bildirən tam ədədi (1\le t\le10^4) verilir.
Hər testin birinci sətrində iki tam və ədədi (1\le n,m\le10^5) verilir.
Növbəti n-1 sətrin hər birində tilin uclarını bildirən iki tam və ədədi (1\le u,v\le n) verilir. Verilmiş tillərin ağac əmələ gətirdiyinə zəmanət verilir.
Bütün testlər üzrə -lərin cəmi 10^5-i keçmir. -lərin cəmi də 10^5-i keçmir.
Hər test üçün bir sətirdə tam ədəd çap edin. -ci ədəd kökü təpəsində olan cəlbedici yerləşdirmələrin moduluna görə sayına bərabər olmalıdır.
Nümunə 1
Nümunə 2
Nümunə 3
Birinci nümunənin birinci testində ağacın bir təpəsi var, buna görə cavab -dir.
Birinci nümunənin ikinci testində kökə ədədi mənimsədilir. Digər təpəyə , və ya mənimsətmək olar, buna görə hər iki kök üçün cavab -dür.
Alt tapşırıq ( bal): t\le10, n,m\le5.
Alt tapşırıq ( bal): n,m\le20.
Alt tapşırıq ( bal): hər təpənin dərəcəsi ən çox -dir.
Alt tapşırıq ( bal): ağac ulduzdur, yəni bütün digər təpələrlə qonşu olan təpə var.
Alt tapşırıq ( bal): n,m\le1000, \sum n\le5000, \sum m\le5000.
Alt tapşırıq ( bal): əlavə məhdudiyyət yoxdur.