Problem Statement:
Ahmed Thabet is one of the previous ACM-ICPC contestants in Cairo University's Faculty of Computers and Information, (Winner of the 2012 ACPC, a participant in the 2013 World Finals in St. Petersburg (Russia), and currently a software engineer at Facebook). In his free time, he likes to socialize with his friends on Facebook. A few days back he wanted to analyze his activity on Facebook and find which friends he interacted with the most. Given his actions on Facebook as strings in one of two forms:

Either "liked X's photo"

or "commented on X's photo"

where X is the name of friend (containing only English upper and lower case letters). Can you help him analyze his activity?

Input Format:
Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 100). Followed by T test cases.

Each test case starts with a line containing two space separated integers N and K representing the number of strings given where each one represents an activity on Facebook, and the a number of friends you are required to output, respectively. There will always be at least K different friends in each test case. (1 ≤ N ≤ 103, 1 ≤ K)

N lines follow, each containing a string S in one of the formats given above. S will consist only of the English alphabet, spaces, and apostrophes ( ' ). S will be, at most, 103 characters.

Output Format:
For each test case print a single line containing "Case n:" (without the quotes) where n is the test case number (starting from 1), then K lines follow, containing the list of Thabet's friends with whom he interacts the most. Ordered in a descending order of interactions, where the first line contains the name of the Friend with the most interactions, the second line contains the name of the Friend with the second most interactions and so on.

Sample Input:
1 6 2 liked Badr's photo liked Shakira's photo liked Badr's photo liked Fegla's photo liked Shakira's photo commented on Shakira's photo

Sample Output:
Case 1: Shakira Badr

Note that in each test-case, Thabet would have interacted with each friend a unique number of times; that is no two friends in the same test-case will have the same number of interactions.

Added by: ahmed_aly
Added at: 2014-04-27 04:51:59 UTC
Time Limit: 3 seconds
Partial score: No
Source:ACM Jordanian Collegiate Programming Contest 2013