There are some chickens and rabbits in the cage. They have fifteen heads and forty feet in all. How many chickens and rabbits are there respectively?

It is a classical math problem which can date back to the Northern and Southern Dynasties (420-589). Here is an interesting algorithm to solve the problem: Assume that the chickens and rabbits are well trained. You whistle, and all of them lift a leg, then there are 40-15=25 feet on the floor. You whistle again, and there are 25-15=10 legs remain standing. After two whistles, all the chickens sit on the floor, and all the rabbits stand on two legs. So there are 10/2=5 rabbits and 15-5=10 chickens.

John has a farm with lots of animals in it. He is now facing the similar problem. There are exactly N kinds of animals and he wants to know their quantities. He only knows that different kinds of animals have different number of legs (at least one), but he has no idea how many legs they each have. He trains the animals and tries to figure it out using the algorithm stated above. First he makes all the animals stand up with all their legs and counts their legs. Then, for each time he whistles, all the animals lift one leg(if it has at least one leg standing on the ground), and then he counts the feet again. After K times, he thinks that it is enough to determine the quantity of each kind of animal, but does it really work? So, it is your job to help him to solve the problem.

Input

The first line contains an integer T (1 ≤ T ≤ 100), indicating the number of test cases.

Each test case contains two lines. The first line contains two integers N (1 ≤ N ≤ 1000) and K (1 ≤ K ≤ 1000), representing the number of different kinds of animals and the time he whistles.

The second line contains K+1 integers A₀ , A₁... A_K (0 ≤ A_i ≤ 10⁴) where A_i represents the number of legs after his i-th whistle.

Output

For each test case in the input, print several lines.

The first line contains "Case #X:", where X is the test case number (starting with 1). The next line contains "No Solution", "Unique Solution" or "Multiple Solutions" according to the result.

If the result is uniquely determined, you should print N extra lines each contains two integer L_i, N_i, where L_i represents how many legs does the i-th kind of animal have and N_i represents the number of i-th kind of animal. The animals should be sorted by the number of their legs in ascending order.

Example

Input:
3
2 3
14 9 6 3
2 2
8 5 3
3 2
20 13 8

Output:
Case #1:
Unique Solution
1 2
4 3
Case #2:
No Solution
Case #3:
Multiple Solutions