You are given a string $S$ containing only uppercase English letters. There are $Q$ queries. Each query can be of two types:

• 1 i: Find the maximum size of the segment [b, e] where 0 ≤ b ≤ i ≤ e < |S| and substring S[b...e] contains only the letter S[i]. A Substring is a contiguous sequence of characters in a string.
• 2 i: Change the character in index i with the character ‘#’.

For both type of queries, S[i] will not contain the character ‘#’.The characters of the string are indexed from 0.

The first line contains number of test cases $T\ (1 ≤ T ≤ 15)$.
For each test cases, the first line contains the string $S\ (1 ≤ |S| ≤ 200,000)$. 
The 2nd line contains number of queries $Q\ (1 ≤ Q ≤ 100,000)$. 
Each of the next $Q$ lines contains one query in the format mentioned in the problem statement.

For each test case, first print the test case number and output of every query of type 1 in a single line.