Modular Enigma

All submissions for this problem are available.

Alice and Bob are a paranoic couple who wants to hold a remote conversation using a chat client. However, they do not like the existent ones (e.g. gtalk, MSN, Facebook chat, etc.), as they think that there might be hidden backdoors in them that allows spies to read their conversations about their never ending love.

Last week, they decided to build their unique chat client, called ABmod, which will encode their messages using a symmetric approach. First, Alice and Bob will choose a public prime integer P and exchange a private key composed of two integers A and B, here 0 <= A,B < P.
To encode a message X they will apply the following function:

where C mod M is the remainder of dividing C between M. This operator satisfy the following properties (among others not mentioned here):

• (A + B) mod M = ((A mod M) + (B mod M)) mod M
• (A x B) mod M = ((A mod M) x (B mod M)) mod M

Eve is in a crush for Bob and wants to spy and interfere his conversation with Alice. To do this, Eve managed to intercept N messages in their plain and encoded forms. Now, she wants to deduce the private key (A,B) to send fake encoded messages to Alice pretending she is Bob. However, she has no idea of how to do it, so she is asking for your help in this task.

Input

The first line contains an integer T, which specifies the number of test cases. Then, T test case descriptions will follow.

Each test case will start with a line with two positive integers, N and P, whose meanings were described previously. The next N lines will contain each 2 integers X_i and Y_i, which represents an intercepted message whose plain form is X_i and encoded form is Y_i.

Output

For each input case you must print the string "Case #i: ", where i is the test case number, starting from 1, followed by the number A and B that compose the private key. If there multiple valid keys, print "MULTIPLE SOLUTIONS" instead. If there are no valid keys, print "NO SOLUTIONS" instead.

Example

Input
4
2 5
3 0
1 4
1 13
0 12
2 2
0 0
0 1
4 97
0 13
1 46
2 79
3 15

Output
Case #1: 3 1
Case #2: MULTIPLE SOLUTIONS
Case #3: NO SOLUTIONS
Case #4: 33 13

Constraints

• T will be between 1 and 1000, inclusive.
• P will be a prime number.
• P will be between 2 and 10⁶, inclusive.
• N will be between 1 and 100, inclusive.
• X_i and Y_i will be between 0 and P-1, inclusive, for all i between 1 and N, inclusive.