Розглянемо граф-дерево. У кожний вузол цього дерева можна помістити одну або декілька фішок. Після розміщення фішок можна вибрати вузол дерева, в якому є дві або більше фішок, і забрати з нього дві фішки, при цьому помістивши одну фішку в довільний з сусідніх вузлів. Таку операцію можна повторювати декілька разів. Ваша задача знайти максимальну кількість фішок (за модулем \textbf{M}), яку можна розмістити на дереві так, щоб виконувалась умова: знайдеться хоча б один вузол дерева, в який буде неможливо помістити жодної фішки за допомогою вказаних операцій. \InputFile У першому рядку міститься кількість тестів \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{100}). Перший рядок кожного тесту містить два числа: \textbf{N} (\textbf{2} ≤ \textbf{N} ≤ \textbf{30000}) -- кількість вузлів у дереві та \textbf{M} (\textbf{2} ≤ \textbf{M} ≤ \textbf{2^31--1}). Далі йде \textbf{N}--\textbf{1} рядків, кожен з яких містить номери двох суміжних вузлів дерева (вузли пронумеровані від \textbf{1} до \textbf{N}), відокремлені пропуском. \OutputFile Виведіть \textbf{T} рядків вигляду "\textbf{Case} #\textbf{A}: \textbf{B}", де \textbf{A} -- номер тесту (починаючи з \textbf{1}), \textbf{B} -- шукана величина для даного тесту.