You are given a binary string s𝑠 of length n𝑛, consisting of zeros and ones. You can perform the following operation exactly once:Choose an integer p𝑝 (1≤p≤n1≤𝑝≤𝑛).Reverse the substring s1s2…sp𝑠1𝑠2…𝑠𝑝. After this step, the string s1s2…sn𝑠1𝑠2…𝑠𝑛 will become spsp−1…s1sp+1sp+2…sn𝑠𝑝𝑠𝑝−1…𝑠1𝑠𝑝+1𝑠𝑝+2…𝑠𝑛.Then, perform a cyclic shift of the string s𝑠 to the left p𝑝 times. After this step, the initial string s1s2…sn𝑠1𝑠2…𝑠𝑛 will become sp+1sp+2…snspsp−1…s1𝑠𝑝+1𝑠𝑝+2…𝑠𝑛𝑠𝑝𝑠𝑝−1…𝑠1.For example, if you apply the operation to the string 110001100110 with p=3𝑝=3, after the second step, the string will become 011001100110, and after the third step, it will become 001100110011.A string s𝑠 is called k𝑘-proper if two conditions are met:s1=s2=…=sk𝑠1=𝑠2=…=𝑠𝑘;si+k≠si𝑠𝑖+𝑘≠𝑠𝑖 for any i𝑖 (1≤i≤n−k1≤𝑖≤𝑛−𝑘).For example, with k=3𝑘=3, the strings 000, 111000111, and 111000 are k𝑘-proper, while the strings 000000, 001100, and 1110000 are not.You are given an integer k𝑘, which is a divisor of n𝑛. Find an integer p𝑝 (1≤p≤n1≤𝑝≤𝑛) such that after performing the operation, the string s𝑠 becomes k𝑘-proper, or determine that it is impossible. Note that if the string is initially k𝑘-proper, you still need to apply exactly one operation to it.InputEach test consists of multiple test cases. The first line contains one integer t𝑡 (1≤t≤1041≤𝑡≤104) — the number of test cases. The description of the test cases follows.The first line of each test case contains two integers n𝑛 and k𝑘 (1≤k≤n1≤𝑘≤𝑛, 2≤n≤1052≤𝑛≤105) — the length of the string s𝑠 and the value of k𝑘. It is guaranteed that k𝑘 is a divisor of n𝑛.The second line of each test case contains a binary string s𝑠 of length n𝑛, consisting of the characters 0 and 1.It is guaranteed that the sum of n𝑛 over all test cases does not exceed 2⋅1052⋅105.OutputFor each test case, output a single integer — the value of p𝑝 to make the string k𝑘-proper, or −1−1 if it is impossible.If there are multiple solutions, output any of them.ExampleinputCopy78 4111000014 2111012 31110001000115 5000006 11010018 40111000112 2110001100110outputCopy3-1754-13NoteIn the first test case, if you apply the operation with p=3𝑝=3, after the second step of the operation, the string becomes 11100001, and after the third step, it becomes 00001111. This string is 44-proper.In the second test case, it can be shown that there is no operation after which the string becomes 22-proper.In the third test case, if you apply the operation with p=7𝑝=7, after the second step of the operation, the string becomes 100011100011, and after the third step, it becomes 000111000111. This string is 33-proper.In the fourth test case, after the operation with any p𝑝, the string becomes 55-proper.

Write a program that takes in a positive integer as input, and outputs a string of 1's and 0's representing the integer in reverse binary. For an integer x, the algorithm is:As long as x is greater than 0 Output x % 2 (remainder is either 0 or 1) x = x / 2Note: The above algorithm outputs the 0's and 1's in reverse order.Ex: If the input is:6the output is:0116 in binary is 110; the algorithm outputs the bits in reverse.

Make Bob WinAlice and Bob are playing a game. They have with them a binary string 𝑆S.Alice and Bob alternate making moves, with Alice going first.On their turn, a player does the following:Choose a non-empty contiguous substring of 𝑆S all of whose characters are the same, delete it from 𝑆S, and concatenate the remaining parts.More formally, choose integers 𝐿L and 𝑅R such that 1≤𝐿≤𝑅≤∣𝑆∣1≤L≤R≤∣S∣ and 𝑆𝐿=𝑆𝐿+1=…=𝑆𝑅S L​ =S L+1​ =…=S R​ , and replace 𝑆S with the string 𝑆1𝑆2…𝑆𝐿−1𝑆𝑅+1𝑆𝑅+2…𝑆∣𝑆∣S 1​ S 2​ …S L−1​ S R+1​ S R+2​ …S ∣S∣​ .This reduces the length of 𝑆S by 𝑅−𝐿+1R−L+1.Alice wins immediately when 𝑆S doesn't contain any occurrence of 11, while Bob wins immediately when 𝑆S doesn't contain any occurrence of 00. Both players will play to win.Note that if the string initially doesn't contain any occurrences of 00, Bob wins before any moves are made.Bob wants to win the game, so before the game starts, he can flip some characters of 𝑆S.That is, Bob can choose an index 𝑖i (1≤𝑖≤𝑁1≤i≤N), and set 𝑆𝑖S i​ to 00 if it was originally 11, and vice versa.Find the minimum number of flips Bob needs to make to ensure he can win.Input FormatThe first line of input will contain a single integer 𝑇T, denoting the number of test cases.Each test case consists of two lines of input.The first line of each test case contains one integer 𝑁N — the length of 𝑆S.The second line contains the binary string 𝑆S.Output FormatFor each test case, output on a new line the minimum number of flips required in 𝑆S to make Bob win.Constraints1≤𝑇≤1051≤T≤10 5 1≤𝑁≤2⋅1051≤N≤2⋅10 5 𝑆S is a binary string, i.e, contains only the characters 00 and 11.The sum of 𝑁N over all test cases won't exceed 2⋅1052⋅10 5 .Sample 1:InputOutput31031116011001101Explanation:Test case 11: Bob changes the only character of 𝑆S, resulting in 𝑆=1S=1.There are no 00's in this string, so Bob wins automatically.Test case 22: There are no 00's in the string, so Bob wins without having to change anything.Test case 33: Bob can flip the first character of the string, turning it into 111001111001.It can be shown that if the game is played on this string, Bob will win; whereas he would lose if the game is played on the initial string.

You are given a binary string s that contains at least one '1'.You have to rearrange the bits in such a way that the resulting binary number is the maximum odd binary number that can be created from this combination.Return a string representing the maximum odd binary number that can be created from the given combination.Note that the resulting string can have leading zeros.

Given a binary string s. Perform r iterations on string s, where in each iteration 0 becomes 01 and 1 becomes 10. Find the nth character (considering 0 based indexing) of the string after performing these r iterations (see examples for better understanding).

You are given a positive integer n.A binary string x is valid if all substrings of x of length 2 contain at least one "1".Return all valid strings with length n, in any order. Example 1:Input: n = 3Output: ["010","011","101","110","111"]Explanation:The valid strings of length 3 are: "010", "011", "101", "110", and "111".Example 2:Input: n = 1Output: ["0","1"]Explanation:The valid strings of length 1 are: "0" and "1".