---{"category_name":"easy","problem_code":"FRIENDGR","problem_name":"Friend Groups In A Line","problemComponents":{"constraints":"- $1 \\leq T \\leq 5\\cdot10^4$\n- $1 \\leq N \\leq 10^5$\n- $0 \\leq K \\leq N$\n- $S$ contains only characters \u0027$0$` and \u0027$1$\u0027\n- The sum of $N$ over all test cases does not exceed $10^6$.\n\n","constraintsState":true,"subtasks":"- 30 points : $1 \\leq R \\leq 10000$\n- 70 points : $1 \\leq R \\leq 10^9$\n","subtasksState":false,"inputFormat":"- The first line of input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.\n- The first line of each test case contains two integers $N, K$.\n- The second line of each test case contains a string $S$.\n","inputFormatState":true,"outputFormat":"For each test case, print a single line containing one integer - the minimum number of friend groups.\n","outputFormatState":true,"sampleTestCases":{"0":{"id":1,"input":"3\n6 2\n010010\n4 0\n1001\n7 2\n1101001\n","output":"1\n2\n1","explanation":"- **Test case $1$:** If the person standing in the $5^{th}$ position moves one position left, the distance between the two people becomes $2$ which is equal to $K$. So they form a friend group.\n\n- **Test case $2$:** If the person standing in the $1^{st}$ position moves one position right and the person standing in the $4^{th}$ position moves one position left, the string becomes \u0022$0110$\u0022, still the distance between them is greater than $K = 0$. So they form two separate friend groups.\n\n- **Test case $3$:** Initially first three people form a friend group and the fourth person forms a separate friend group. Now if the fourth person moves one position left, he becomes a friend of the third person as the distance between these two people is equal to $2$, and hence all the four people belong to one friend group.","isDeleted":false}}},"video_editorial_url":"https://youtu.be/sO36s2neMFI","languages_supported":{"0":"CPP14","1":"C","2":"JAVA","3":"PYTH 3.6","4":"CPP17","5":"PYTH","6":"PYP3","7":"CS2","8":"ADA","9":"PYPY","10":"TEXT","11":"PAS fpc","12":"NODEJS","13":"RUBY","14":"PHP","15":"GO","16":"HASK","17":"TCL","18":"PERL","19":"SCALA","20":"LUA","21":"kotlin","22":"BASH","23":"JS","24":"LISP sbcl","25":"rust","26":"PAS gpc","27":"BF","28":"CLOJ","29":"R","30":"D","31":"CAML","32":"FORT","33":"ASM","34":"swift","35":"FS","36":"WSPC","37":"LISP clisp","38":"SQL","39":"SCM guile","40":"PERL6","41":"ERL","42":"CLPS","43":"ICK","44":"NICE","45":"PRLG","46":"ICON","47":"COB","48":"SCM chicken","49":"PIKE","50":"SCM qobi","51":"ST","52":"SQLQ","53":"NEM"},"max_timelimit":1,"source_sizelimit":50000,"problem_author":"soumyadeep_21","problem_tester":"","date_added":"12-08-2021","tags":{"0":"easy","1":"easy","2":"greedy","3":"greedy","4":"soumyadeep_21","5":"start9","6":"start9"},"problem_difficulty_level":"Unavailable","best_tag":"","editorial_url":"https://discuss.codechef.com/problems/FRIENDGR","time":{"view_start_date":1629221400,"submit_start_date":1629221400,"visible_start_date":1629221400,"end_date":1735669800},"is_direct_submittable":false,"problemDiscussURL":"https://discuss.codechef.com/search?q=FRIENDGR","is_proctored":false,"visitedContests":{},"layout":"problem"}---### Read problem statements in [Mandarin Chinese](https://www.codechef.com/download/translated/START9/mandarin/FRIENDGR.pdf) and [Bengali](https://www.codechef.com/download/translated/START9/bengali/FRIENDGR.pdf).There are $N$ positions in a queue. Given a *binary string* $S$ of length $N$, where $S_i =$ `'$1$'` denotes, there is a person standing in the $i^{th}$ position.The distance between two people standing in the $i^{th}$ and $j^{th}$ positions respectively in the queue is $\mid i - j \mid$, where $\mid x \mid$ denotes the absolute value of $x$. Now, two people are considered to be friends if they are at a distance less than or equal to $K$.Let's say, there are $M$ people, $P_1, P_2, \dots, P_M$ standing one after another in a queue such that for each $1 \leq i \lt M$, $P_i$ and $P_{i+1}$ are friends, then all the $M$ people are considered to be in a *friend group*.For example, consider the string $S =$ `"$1101001$"` and $K = 2$.Let's denote the people standing in the $1^{st}$, $2^{nd}$, $4^{th}$ and $7^{th}$ positions in the queue by $P_1, P_2, P_3, P_4$ respectively. Now, $P_1$ and $P_2$ are friends as the distance between them is $1$, $P_2$ and $P_3$ are also friends as the distance between them is $2$. $P_4$ is not friend with anyone. Hence $P_1, P_2, P_3$ form a friend group and $P_4$ forms a separate friend group.Now each person can move one position right or one position left or stay in the same position. However, they can't move out of the queue. Find the *minimum* number of friend groups they can form if they move optimally.It is possible that there is more than one person standing in the same position after the movements.<aside style='background: #f8f8f8;padding: 10px 15px;'><div>All submissions for this problem are available.</div></aside>