Tokens

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.

Input

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

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

Output

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.