This year, Egypt has been going through an extremely challenging stage. The parliamentary elections are about to take place according to a newly introduced election laws. The seats of the parliament are going to be divided in a party-list proportional representation. This type of elections allows voters to vote for a party (not for individual candidates). Each party wins a number of seats which depends on the number of votes they received.

You are the president of the ACM party in your electoral district (Association of Corrupt Murderers) and you want your party to win as much seats as possible in the coming elections. You know exactly how many people will vote for every party (including yours), thanks to your amazing prediction abilities.

There are two proposed voting systems (explained later) and it is not yet decided which of them is going to be used. You can use your connections trying to influence the decision of which voting system is put to use. Assuming your prediction is completely correct, the problem is to find the voting system that will let your party win more seats.

Voting System 1: D'Hondt method

This system is used in many countries, including Turkey, Japan and Spain. Let's say there are P parties and S seats. This method creates a grid of numbers, with P rows and S columns, where the entry in the i-th row and j-th column is the number of votes won by the i-th party divided by the number j. The first seat is given to the party that has the entry with the highest value. The second seat is given to the party that has the entry with the second highest value, and so on. If two or more entries have the same value, then the seat is given to the party that occurs first in the input file (for the simplicity of this problem).

 

For example: if 5 seats are to be allocated, divide each party's total votes by 1, then by 2, 3, 4 and 5. An example is given in the table below. The 5 highest five entries are highlighted in bold, ranging from 70.0 down to 30.0. The tie between party B and party D is resolved by giving the seat to B as it occurs first in the input. For each cell in bold, the corresponding party gets a seat.

Party	Number of received votes (V)	V/1	V/2	V/3	V/4	V/5	Seats won
A	70	70	35	23.3	17.5	14	2
B	60	60	30	20	15	12	2
C	50	50	25	16.7	12.5	10	1
D	30	30	15	10	7.5	6	0

 

Voting System 2: Sainte-Laguë method

This system is used in fewer countries, including Norway, Sweden and Germany. This method favors smaller parties more than D'Hondt method. After the votes to each party has been counted, the parliament seats are given in an iterative way, one by one to the party that has the highest quotient. The quotient of a party is calculated by this formula: quot = V / (2s+1)

Where:

V: is the total number of votes that party received, and

s: is the number of seats that party has been allocated so far, initially 0 for all parties.

 

For simplicity, if two or more parties are tied because they have the same quotients, the party that occurs first in the input file is given the  next seat allocated. The quotients are recalculated after each seat has been given and this process is repeated until all seats have been allocated.

Example: using the same example from before, in the table below:

Party	Number of received votes (V)	quot in round 1	quot in round 2	quot in round 3	quot in round 4	quot in round 5	Seats won
A	70	70	23.3	23.3	23.3	23.3	2
B	60	60	60	20	20	20	1
C	50	50	50	50	16.7	16.7	1
D	30	30	30	30	30	10	1

The cells in bold represent the highest quotient for this seat and their party wins a seat correspondingly.

Input Specification:

First line of the input will contain T, the number of test cases. T test cases follow. The first line of each test case contains two integers N and S, separated by a single space. N is the number of parties and S is the number of seats to be allocated, 2  ≤ N, S ≤ 10,000. Each of the next N lines contains the name of the party P[i], a unique string of at most 20 lowercase and upper case English letters, followed by a single space, then an integer V[i], the exact number of predicted votes to be earned by this party. 0  ≤ V[i] ≤ 10^9 (1,000,000,000). The number of earned votes may be delimited by comas (e.g. could be 127 or 12,7). “ACM” will exist as a party name exactly once in every input case.

Output Specification:

For each test case, output a single line of output in the form “Case K: Method” where K is the number of the test case and Method is “S”, “D”, or “No difference”.

Method = “D” if D'Hondt method wins the ACM party more seats. Method = “S” if Sainte-Laguë method wins the ACM party more seats. If both methods result in the same seat count for your party, then method = “No difference”.

Sample input:

1

6 10

Yellow 47000

White 16000

Red 15900

ACM 12000

Blue 6000

Pink 3100

Sample Output:

Case 1: No difference