Tau Team is a team from FCIS-ASU consists of three members: Mohamed Salama, Ahmed Mohsen and Ahmed Ameen. This team participated in ACM ACPC (Arab Collegiate Programming Contest) 2013 and got 10th place and ranked as 7th university.

Unfortunately, after the announcement of the results Mohammed Foad “the organizer of ACM ACPC” announced that the first 6 universities only will qualify to ACM ICPC (International Collegiate Programming Contest) which will take place in June 2014 in Russia. Tau Team was disappointed because they will not participate in ACM ICPC this year.

Ahmed Ameen was very sad and went to sleep this day. He dreamed that they qualified to ACM ICPC and he was in the world final contest with his team. When he read the first problem he was shocked because it was very hard and he could not solve it. He gave it to Ahmed Mohsen. Ahmed Mohsen read it and suddenly he fainted and fell on the floor. Mohamed Salama left Ahmed Mohsen on the floor and took the problem from him. When Mohamed Salama read it he started to cry. The 5 hours passed and the contest ended. They didn’t solve any problem. Suddenly Ahmed Ameen woke up terrified and thanked Allah that they will not participate in ACM ICPC this year and decided to train more to participate next year Insha'Allah and do better than the dream. Ahmed Ameen remembered the problem which was in the dream and asked you to help him to solve it. The problem is that you have a string S and 2 types of queries.

The first type of query consists of 2 substrings of S: Start and Goal and you're asked to determine the minimum cost to convert the Start substring into the Goal substring, you’re allowed to do any of the following operations on the Start substring any number of times:

• 1 - insert a character costs 3
• 2 - delete a character costs 2
• 3 - change a character costs 1
• 4 - swap any two characters costs 0

Note: These four operations will not change the original string S.

The second type of query requires you to change all characters of S with this equation
S[i] = char ( (219+( (S[i]*10)%S[i] ) ) - S[i] )

Input

Your program will be tested on one or more test cases. The first line of input will be a single integer T, the number of test cases (1<=T<=10). Followed by string S consists of lower case letters only (max number of characters = 10^5) and an integer Q (max value = 10^5 indicates the number of Queries).

The first type of queries will be in this format: “1 Start_i Start_j Goal_i Goal _j”, Where

• Start_i: is an integer indicates the index of the beginning of the Start substring.
• Start_j: is an integer indicates the index of the end of the Start substring.
• Goal_i: is an integer indicates the index of the beginning of the Goal substring.
• Goal_j: is an integer indicates the index of the end of the Goal substring.

And the second type format is “2 Change” to change the original string S.

You can assume that:

• The start substring always precede the goal substring in string S.
• The two substrings will not overlap.
• All indices will be 1 based and valid.

Output

For each test case, print "Case_#i:" where “i” is the number of the test case (starting with 1) and "_" is a space. Then print Q Lines the j’th line corresponding to the j’th query. For the queries of the first type print an integer giving the minimum cost for conversion and for the queries of second type print the word “Done".

Example

Input:
1
aabzczbaadc
4
1 1 5 6 11
1 1 3 4 7
2 Change
1 4 7 8 11

Output:
Case #1:
3
5
Done
3