Alice had a bag where each number from 1 to N was present in it. After a magic trick she either removes all even numbers or all odd numbers from the bag.

 

Given the kind of trick she has performed find the P^th smallest number in the bag after the trick. For example P = 1 denotes the smallest number present.

 

Input

 

First line contains T, the number of test cases. Each test case consists of N, a string S and an integer P in single line.

 

S will be either “odd” or “even”(quotes for clarity), denoting the kind of trick Alice has performed.

 

Note: It is guaranteed that P will be less than or equal to remaining items in the bag.

 

Output

 

For each test case, print the required answer in one line.

 

Constraints

 

Should contain all the constraints on the input data that you may have. Format it like:

 

• 1 = T = 100
• 1 = N = 10³
• P = 1

 

 

Example

Input: 2 4 odd 2 5 even 2 Output: 4 3

 

Explanation

 

Example 1.
After performing the “odd” trick the numbers 1 and 3 get removed from the bag.
Numbers 2 and 4 are left in the bag.
2nd smallest number is 4 now.

 

Example 2.
After performing the “even” trick the numbers 2 and 4 get removed from the bag.
Numbers 1, 3 and 5 are left in the bag.
2nd smallest number is 3 now.

q2

Little Toojee was a happy go lucky boy. He seemed to find most, if not all, things funny. One day he read a word and started laughing a lot. Turns out that the word consisted only of the letters L and O. Whenever he saw the subsequence ‘LOL’ in the word, he laughed for 1 second. Given t strings, find out for how long Toojee laughed on seeing each string.

 

Input

 

The first line contains t queries.
This is followed by t lines each containing one string S. String S consists only of capital letters.

 

Output

 

Output for each string on a new line.

 

Constraints

 

Should contain all the constraints on the input data that you may have. Format it like:

 

• 1 = t = 10
• 1 = |S| = 10⁶

 

 

Example

Input: 2 LOL LOLOL Output: 1 4

 

Explanation

 

Test 1: On observation, we can tell that there is only 1 occurrence of LOL.

Test 2: Let the string be 0-indexed and let V = {a, b, c} denote the indices that make up the string “LOL”, where a is index of the 1st ‘L’, b is index of the ‘O’ and c is the index of the 2nd ‘L’.
So, V can be {0, 1, 2}, {2, 3, 4}, {0, 1, 4} and {0, 3, 4}. We see that there are 4 occurrences of the string “LOL”.