Given a string S indexed from **1 to N**. Given **character ch** and **number of repetition r**.

There are two types of queries

L ch r - the largest index from 1 to N where there is exactly r repetition of character ch.

S ch r - the smallest index from 1 to N where there is exactly r repetition of character ch.

An index always **exists** for each query.

Input Format

For each test case T.

Contains a string S and the next line contains Q the number of queries.

Followed by Q lines of queries

Sample Input

1

aabbabb

2

L a 2

S a 2

Sample Output

4 (indexed from 1 to N)

2