Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Road to MUZAN

By Riadh_Hasan · Limits 1s, 512 MB

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 NN length string and QQ queries where ii -th character will be changed permanently with CC 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 TT which is the number of test cases. Then in every test case, in the first line there will be one integers NN. The next line will contain a string of size NN (without any space) only containing lowercase English letters. Then in the next line an integer QQ will be given. Then each of the next QQ lines will contain one integer ii and one character CC which is also a lowercase English letter.

Constraints:

1T301 ≤T ≤30

1N,Q1051 ≤ N, Q ≤10^5

1in1 ≤ i ≤ n

Output

For every test case first print “CaseX:Case X:”(without quotes) where XX 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

InputOutput
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.

    Discussion

    Statistics


    83% Solution Ratio

    showrov_couEarliest, 5d ago

    n3wb13_223Fastest, 0.3s

    alamkhanLightest, 18 MB

    steinumShortest, 631B

    Submit

    Login to submit