Given a number $m$ of length $n$, you need to determine the format of $m$ when it is split by commas every $k$ digits, starting from the lowest digit (the rightmost) to the highest.

Input

The problem contains multiple test cases. The first line contains two positive integers $c$ and $t$, representing the Subtask ID and the number of test cases, respectively. Specifically, for the sample, $c = 0$.

For each test case:

• Input one line containing three positive integers $n, m, k$.

Output

For each test case:

• Output one line containing a string representing your answer.

Examples

Input 1

0 2
13 1145141919810 3
10 1114561523 4

Output 1

1,145,141,919,810
11,1456,1523

Note 1

For the first test case, following the problem description, the split number string is 1,145,141,919,810.

For the second test case, following the problem description, the split number string is 11,1456,1523.

Constraints

For all data, it is guaranteed that:

• $1 \le t \le 10^5$;
• $1 \le k < n \le 10^6$;
• $\sum n \le 10^6$;
• $10^n \le m < 10^{n+1}$.

This problem uses bundled testing. The special properties of each subtask are as follows: