The war was terrible, thousands of humans and rainbow people lying down on the streets. Ronny didn’t know what to do, so he decided to go and search for the Rainbowland Castle and talk to the King. The rainbowlandians stared at Ronny with caution, waiting him to do something bad just to get him and rainbow-kill him. Finally, Ronny made it to the King’s room and talked to him about stopping this horrible war. The King accepted Ronny’s proposal, but only with one condition, Ronny needed to prove once again what human beings were capable of. The King said that if Ronny answered the Q queries that he had for him about an order line of rainbow people numbered from 1 to N , he and his nation would go away. These rainbow people had a letter with a number on it (Initially this number it’s 0).

There are two types of queries, modification queries and answer queries. The modification queries consists on, given an interval from A to B inclusive ([A,B]), Ronny needed to update those rainbow people’s letter, adding one to the number on it; so, by instance, if the interval is [1,2], then Ronny needed to add one to the first and second rainbowlandian on the line. The answer queries consists on, given an interval from A to B inclusive, Ronny should say the sum of every rainbow people’s letter.

If Ronny can do this, the humans are saved! So he need your help, because he is not really that good in maths and fast sums.

Input

The first line contains an integer T, which specifies the number of test cases. Then will follow the descriptions of T test cases.

For each test case you will get an integer N and an integer Q, that represents the number of rainbowlandian in the line and the number of queries the King asks for. Then, Q lines will follow, each containing a string and 2 integers, the type of query, that can be "modification" or "answer" (Quotes for clarity), the first and the last rainbowlandian that Ronny must have< in mind in order to answer the query.

Output

For each input case you must print the string "Scenario #i:" where i is the number of the test case (Starting by 1), followed by Q lines with the answer of each query. If the query was a modification query, then you should output "OK" (Quotes for clarity), otherwise, output the sum of the number from A to B inclusive.

Sample

Input:
2
4 4
answer 1 4
modification 1 2
modification 2 3
answer 2 2
8 6
modification 2 4
modification 4 8
modification 4 5
answer 8 8
modification 5 7
answer 4 8

Output:
Scenario #1:
0
OK
OK
2
Scenario #2:
OK
OK
OK
1
OK
11

Constraints

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 100,000
• 1 ≤ Q ≤ 100,000