Helping Beksin Jho

Beksin Jho is a very talented boy. Like all of you guys, he also has great interest in programming and problem solving. That’s why he always spends his leisure time in learning new algorithms and techniques for solving different problems. Recently he started working with strings in C++ and has learned how to find if a string $S$ is a substring of $T$ or not. He wrote the following function to check and count how many times string $S$ occurs as a substring in string $T$:

int occur(string s, string t){
    /* Finds how many times s occurs in t as substring */
    int ans = 0;

    for (int i = 0; i < t.length(); i++){
        int ti = i, sj = 0;
        
        while(ti < t.length() && sj < s.length() && t[ti] == s[sj]){
            ti++;
            sj++;
        }
        if (sj == s.length()){
            ans ++;
        }
    }
    return ans;
}

One day, one of his teacher at school saw this code. The teacher asked Beksin, “Can your this piece of code handle a large amount of data?”. Beaksin thought a little bit and confidently said, “Yes sir. It can”. His teacher smiled a little and replied, “Okay! Lets see. I will give you a task to solve. You have to generate the output and show that to me. But, you have one constraint, your program will just get a fixed amount of time (problem’s time limit) to generate the whole output. You can use this piece of code or can modify the “occur()” function if you wish. If you can solve this problem, I will give you a chocolate.” After that, the teacher described the task in detail:

Assume that Beksin Jho has an empty array: $A$ ($1 \le |A| \le 100000$) and his code has to perform two types of queries:

Type 1: He will be given a string $S$. If the string already exists in the array $A$, then he needs to skip this query, otherwise just append string $S$ at the end of array $A$.

Type 2: Beksin will be given a string $T$ and two integer - $L$ & $R$. Now, he has to output the value of the following equation:

It is guaranteed that $L$ & $R$ will always be valid.

Beksin Jho worked very hard to solve this problem. He tried a lot to reuse his above piece of code. But alas! He never ended up with success. Everytime he ran his code against the data given by his teacher, it fails to output all the results within time. ☹️

Somehow, Beksin Jho came to know that you three guys are a team and can solve many hard and difficult problems. So, he ran towards you asking for help. Can you guys help him out?

Input

The first line of the input will contain a single integer $TS$ ($1 \le TS \le 5$), denoting the number of test cases. Each test case starts with a single integer $N$ ($1 \le N \le 100000$), which represents the number of queries to perform in this testcase. After that, $N$ lines follows. Each line contains one of the following two types:

• 1 S - Denoting the first type of query ($1 \le |S| \le 100000$)
• 2 T L R - Denoting the second type of query ($1 \le |T| \le 100000$, $1 \le L \le R \le |A|$)

Strings $S$ and $T$ will only contain lowercase letters. It is guaranteed that the summation of length of all the strings in a single test case will not cross 1000000.

Output

The first line for each test case should contain the test case number in this format: Case X:. Here $X$ is the number of current test case. Then for each of the queries of type 2, you have to print separate lines containing the result.

Sample

Input	Output
1 8 1 ab 2 a 1 1 1 a 2 a 1 2 1 bc 2 abc 1 3 2 abac 1 3 2 aabc 2 3	Case 1: 0 1 3 3 3