It's English class now. So John is bored as usual. To get over his boredom he is doing a very strange thing. He writes an arbitrary string on his notebook and then keeps changing a single character of the string every time and tries to find out if the string has become a palindrome.

As John is very smart this task is very simple for him.

But how simple is it for you? Can you be as smart as the great John?

You'll have to write a code that solves the similar problem and hopefully, as fast as John.

Input

First line of the input will be an integer T (T <= 15) denoting number of test cases.

Each test case starts with an integer N (1 <= N <= 100000) denoting the length of the string.

Next line will contain the string consisting of only small letters of English alphabet (a, b, c, ... x, y, z).

Then there will be another integer M (1 <= M <= 10000) denoting number of queries.

Each query will be in the form: i x, where i will be an integer (1 <= i <= N) and x will be a character, (a <= x <= z) and it will mean that the i-th character of the string has been changed to x.

Output

First you will have to print the test case number.

Then for each query in the test case you will have to print "YES" if the given string has become a palindrome. Otherwise print "NO" (without the quotes.)

See sample input/output and explanation for details.

Sample

Input
1
11
madamimadam
6
6 z
1 a
11 b
5 z
1 b
7 z

Input
Case 1:
YES
NO
NO
NO
NO
YES

Explanation:

After the 1st query the string is: madamzmadam, which is a palindrome

After the 2nd query the string is: aadamzmadam, which is NOT a palindrome

After the 3rd query the string is: aadamzmadab, which is NOT a palindrome

After the 4th query the string is: aadazzmadab, which is NOT a palindrome

After the 5th query the string is: badazzmadab, which is NOT a palindrome

After the 6th query the string is: badazzzadab, which is a palindrome