There is a ring consisting of n lights numbered as 1, 2, …,n (as shown in figure 1 ). At time 0, some lights are on and the others are off. At time t+1, light i alters its status (from on to off or from off to on), only if light i-1 is on at time t (for i=1, light i-1 means light n). Please work out the status of each light at time m.
The first line of the input is an integer k denoting the number of test cases. The following 2k lines are input data. Each test case includes two lines. The first line consists of two integers separated by one space, where the first integer n (0<n<=10^4) denotes the number of lights and the second integer is m (0<m<=10^4). The second line is a binary string of length n, representing the status of each light in time 0 ( "1" denoting the light is on and "0" denoting the light is off ).
For each test case, output a line containing a binary string representing the status of each light at time m.