Sub String Manipulation

All submissions for this problem are available.
Description
Ram was given a puzzle by his brother. Ram's brother has two sets of cards. One consist of the string S and another consist of the string P, where P and S are lowercase English characters. P is the substring of S. Ram's brother has set of Q queries that are needed to be performed on the strings P and S. The query is of the form N and C where N is a positive integer and C is a lowercase character.
For every query Q_{i}, Ram's work is to change the index value N (Assume 0 based indexing) of the string S to the character C.
The Query will be executed in the order. Ram's work is to find the minimum number of queries that are executed sequentially from the start so that the string P no longer exist as a substring in S.
If the String P exist in S even after executing all the Q queries then return the answer as 1.
Help ram to solve the puzzle.
Input Format
First line contains a single integer T denoting the number of test cases.
First line of each test case contains a single string S.
Second line of each test case contains a single string P
Third line of each test case contains a single integer Q defining the number queries.
The next Q lines of the test case contains N and C which are space seperated.
Constraints
1 ≤ T ≤ 50.
1 ≤ S ≤ 2.10^{5}.
1 ≤ P ≤ S.
1 ≤ Q ≤ S.
0 ≤ N ≤ S.
Output Format
For each testcase T, return a single integer denoting the minimum number of queries after which the string P ceases to exist in string S.
Example Input
2
abcde
bc
3
0 p
1 q
2 w
abcde
cde
2
0 t
1 z
Example Output
2
1
Explanation
Test Case 1
Here S is a[bc]de.
Here P is bc.
After the 1^{st} query the S is p[bc]de.
After the 2^{nd} query the S is p[qc]de, now the string P is not in string S, so after the 2^{nd} query S is changed so the answer is 2.
Test Case 2
Here S is ab[cde].
Here P is cde.
After the 1^{st} query the S is tb[cde].
After the 2^{nd} query the S is tz[cde].
Even, after all the updates the string P is in the string S, so the answer is 1.
Author:  vijaykumarakv 
Tags  vijaykumarakv 
Date Added:  23122018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions