eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Фишки

Фишки

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

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

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

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

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

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

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

Пример

Входные данные #1
2
6 997
1 2
1 4
3 4
5 3
3 6
7 13
1 2
1 3
1 4
2 5
3 6
4 7
Выходные данные #1
Case #1: 16
Case #2: 5