favorite We need a little bit of your help to keep things running, click on this banner to learn more



Consider a tree-graph. In each node of this tree one or more tokens can be placed. After the placement a node with two or more tokens can be selected and two tokens can be removed from the selected node and one token can be placed to any adjacent node to the selected one. Such operation can be repeated several times. Your task is to find the maximal number of tokens (modulo M) that can be placed on the tree nodes to fulfill the following condition: there exists at least one node, to which it is impossible to move a token applying given operations.


First line of input contains the quantity of tests T (1T100).

First line of each test case contains two numbers: N (2N30000) – the number of nodes in the tree and M (2M31–1 ≤ 2). Then N1 lines follows, each of which contains 2 adjacent node numbers (nodes are numbered from 1 to N) separated by space.


Output T lines of the form "Case #A: B", where A is the number of test (beginning from 1), B is the desired number for this test case.

Time limit 2 seconds
Memory limit 64 MiB
Input example #1
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
Output example #1
Case #1: 16
Case #2: 5