There is a big wall beside Bangladesh University Of Business and Technology (BUBT). The student of CSE wants to color it with many colors. So the students of CSE want permission to color the wall from Dipu Sir. Dipu Sir not only gives permission, but also he maintains this:

The wall is L meter long. Every student can do any of the following two operations:

1. He can color the wall from i to j meter by a color.
2. Otherwise he can count the different numbers of color from i to j meter.

In this problem you have given length of wall number of student you have to do same task here.

Input

Input starts with an integer T (≤ 25), denoting the number of test cases.

Each test case contains two integers. The first integer means number of students N (2 <= N <= 100), and the second integer means the length of wall L (1 < L < 1000).

Next N lines contain work done by nth Student. Each line contain a word (color or report).

1. If the word is color than you have a color (A <= Color <= Z), and index i and j.
2. If the word is report than there is two integer i and j you have to report how many different color form i to j.

You can assume that at first the full wall is color A.

Output

For each case, print the case number and next lines print the reports.

Example

Input:
1
5 5
Color F 1 2
Color B 2 4
Report 1 4
Color C 4 5
Report 1 5

Output:
Case 1:
2
3

Problem Setter: Shipu Ahamed, Dept. of CSE
Bangladesh University of Business and Technology (BUBT)