Road to MUZAN

From the earliest times, humanity knows about human-eating monsters, lurking in the darkness to devour an unfortunate soul. The origin of those demons came from one name named ‘Kibutsuji Muzan’ who is the king of the demons. Now to stop the monstrosity of the demons a secret organization named ‘Demon Slayer Corps’ started to look for skilled swordsmen who can kill the demons. Now a boy named Tanjirou joined the Demon Slayer Corps so that he can cure his sister who has been transformed into a demon due to Muzan’s attack and to slay Muzan once and for all.

Now Muzan is a very tricky demon who can shapeshift (change his look and body shape) and nobody can find him easily. But one day Tanjirou and his friends find out a clue that when Muzan shapeshifts he also has to choose a name for his new form. The interesting part of the clue was that whenever he chooses a name, he chooses the longest palindromic string that can be formed with the characters from the name. The palindromic string is a sequence that reads the same backwards as forwards

Now, Tanjirou recognized you as the most talented programmer and a trustful friend. He has given you an $N$ length string and $Q$ queries where $i$ -th character will be changed permanently with $C$ in each query. Now write a program that will give you the length of the longest palindrome string that can be formed after every query.

Input

The first line of the input will contain an integer $T$ which is the number of test cases. Then in every test case, in the first line there will be one integers $N$. The next line will contain a string of size $N$ (without any space) only containing lowercase English letters. Then in the next line an integer $Q$ will be given. Then each of the next $Q$ lines will contain one integer $i$ and one character $C$ which is also a lowercase English letter.

Constraints:

$1 ≤T ≤30$

$1 ≤ N, Q ≤10^5$

$1 ≤ i ≤ n$

Output

For every test case first print “$Case X:$”(without quotes) where $X$ is the test case number. Then from the next line print the length of the longest palindromic string that can be formed with the characters from the current string after every query. Check out the samples for clarification.

Sample

Input	Output
2 8 abcacbac 3 1 c 1 a 2 d 4 abaa 2 3 b 1 c	Case 1: 8 7 5 Case 2: 4 3

Note: Dataset is huge, use faster I/O methods.