Рассмотрим граф-дерево. В каждый узел этого дерева можно поместить одну или несколько фишек. После расположения фишек можно выбрать узел дерева, в котором есть две или больше фишек, и убрать из него две фишки, при этом поместив одну фишку в любой из соседних узлов. Такую операцию можно повторять несколько раз. Ваша задача найти максимальное количество фишек (по модулю M), которое можно разместить на дереве так, чтобы выполнялось условие: найдётся хотя бы один узел дерева, в который будет невозможно поместить ни одной фишки с помощью указанных операций.

   Входные данные

   Первая строка ввода содержит количество тестов T (1 ≤ T ≤ 100).

   Первая строка каждого теста содержит два числа: N (2 ≤ N ≤ 30000) – количество узлов в дереве и M (2 ≤ M ≤ 2³¹–1). Далее следует N–1 строка, каждая из которых содержит номера двух смежных узлов дерева (узлы занумерованы от 1 до N), разделённых пробелом.

   Выходные данные

   Выведите T строк вида "Case #A: B", где A – номер теста (начиная с 1), B – искомая величина для данного теста.