Preflix Zeros Solution|codesheff lunchtime 2022 for div 3

You are given a string S$S$ of length N$N$, which consists of digits from 0$0$ to 9$9$. You can apply the following operation to the string:

• Choose an integer L$L$ with 1≤L≤N$1\le L\le N$ and apply Si=(Si+1)mod10$S_i=(S_i+1)\mathrm{mod}10$ for each 1≤i≤L$1\le i\le L$.

For example, if S=39590$S=39590$, then choosing L=3$L=3$ and applying the operation yields the string S=406––––90$S=\underset{\_}{406}90$.

The prefix of string S$S$ of length l(1≤l≤∣S∣)$l(1\le l\le \mid S\mid )$ is string S1S2…Sl$S_1{S}_2\dots S_l$. A prefix of length l$l$ is called good if S1=0,S2=0,…,Sl=0$S_1=0,S_2=0,\dots ,S_l=0$. Find the length of the longest good prefix that can be obtained in string S$S$ by applying the given operation maximum K$K$ times.

Input Format

• The first line of input contains an integer T$T$, denoting the number of test cases. The T$T$ test cases then follow:
• The first line of each test case contains two space-separated integers N,K$N,K$.
• The second line of each test case contains the string S$S$.

Output Format

For each test case, output in a single line the length of the longest good prefix that can be obtained in string S$S$ by applying the given operation maximum K$K$ times.

Constraints

• 1≤T≤105$1\le T\le {10}^5$
• 1≤N≤105$1\le N\le {10}^5$
• 0≤K≤109$0\le K\le {10}^9$
• ∣S∣=N$\mid S\mid =N$
• S$S$ contains digits from 0$0$ to 9$9$
• Sum of N$N$ over all test cases does not exceed 3⋅105$3\cdot {10}^5$.

Subtasks

• Subtask 1 (100 points): Original constraints

Sample Input 1 

6
3 5
380
3 9
380
4 2
0123
5 13
78712
6 10
051827
8 25
37159725

Sample Output 1 

0
3
1
3
2
5

Explanation

Test case 1$1$: There is no way to obtain zeros on the prefix of the string S=380$S=380$ by applying the given operation maximum 5$5$ times.

Test case 2$2$: The optimal strategy is: choose L=2$L=2$ and apply the operation twice, resulting in S=500$S=500$, then choose L=1$L=1$ and apply the operation 5$5$ times, resulting in S=000$S=000$.

Test case 4$4$: One of the possible sequence of operations is the following:

• Choose L=5$L=5$ and apply the operation thrice, resulting in S=01045$S=01045$.
• Choose L=2$L=2$ and apply the operation 9$9$ times, resulting in S=90045$S=90045$.
• Choose L=1$L=1$ and apply the operation once, resulting i
• Solution

   This question solution is updated within contest time. please click on follow button and subscribe our channel.if you follow and subscribe our channel then get notification of answer as soon as possible.

• S=00045