Charity Walkathon Badge Generation

You are organizing a charity walkathon event and need to generate unique badge representations for each participant. Each badge consists of the participant's ID and a unique short name based on their first and last names. The short name is created by taking the minimum prefix from the participant's first name and appending the full last name, ensuring that within the same last name group no two badges are identical. Formally, if a participant has first name \(F\) and last name \(L\), then the badge string is determined as \(\text{prefix}(F,k)+L\) where \(k\) is the smallest positive integer such that the badge has not been used before for any other participant with last name \(L\).

The input begins with an integer \(T\) representing the number of test cases. For each test case, an integer \(M\) is provided which specifies the number of participants, followed by \(M\) lines each containing a participant's record in the format: ID FirstName LastName. The output for each test case should list the badges, one per line, formatted as ID Badge in the same order as the participants appear in the input.

inputFormat

The input is provided via stdin. It consists of multiple test cases. The first line contains an integer \(T\), the number of test cases. For each test case, the first line contains an integer \(M\) (the number of participants in the test case). The following \(M\) lines each contain a participant record with three fields separated by spaces: the participant's ID (an integer), first name, and last name.

Example:

1
3
1 John Doe
2 Jane Doe
3 Jack Doe

outputFormat

Output the generated badges to stdout. For each participant, print a line containing the participant's ID and the generated badge separated by a space. The order of output lines should match the input order.

Example:

1 JDoe
2 JaDoe
3 JacDoe

## sample

1
3
1 John Doe
2 Jane Doe
3 Jack Doe

1 JDoe
2 JaDoe
3 JacDoe

</p>