Frequency Analysis of Letters

Given a string of lowercase English letters, count the frequency of each letter and output the top \( k \) letters with the highest frequency. In case of a tie, letters must be sorted in alphabetical order.

Mathematically, if the frequency of a letter \( x \) is given by \( f(x) \), then the letters should be sorted based on the tuple \( (-f(x), x) \). For each test case, output the results as "letter: frequency" pairs on separate lines. The outputs for multiple test cases are concatenated sequentially.

Constraints:

• \(1 \le T \le 10\), where \(T\) is the number of test cases.
• For every test case, \(1 \le |s| \le 10^5\), where \(s\) is the input string.
• \(1 \le k \le 26\).

inputFormat

The input is read from stdin and has the following format:

1. The first line contains an integer \(T\), the number of test cases.
2. For each test case, there are two lines:
   1. A string \(s\) of lowercase English letters.
   2. An integer \(k\), indicating how many of the most frequent letters to output.

outputFormat

For each test case, output exactly \(k\) lines. Each line should display a letter and its frequency in the format "letter: frequency". Letters are listed in descending order of frequency, and in cases where frequencies are equal, in alphabetical order. The outputs for different test cases are concatenated sequentially.

## sample

4
apple
2
banana
3
aabbcc
2
abcdefg
3

p: 2
a: 1
a: 3
n: 2
b: 1
a: 2
b: 2
a: 1
b: 1
c: 1

</p>