Consider the following process. You have a binary string (a string where each character is either 0 or 1) w of length n and an integer x. You build a new binary string s consisting of n characters. The i-th character of s is chosen as follows:

  * if the character w_{i-x} exists and is equal to 1, then s_i is 1 (formally, if i > x and w_{i-x} =  1, then s_i =  1); 
  * if the character w_{i+x} exists and is equal to 1, then s_i is 1 (formally, if i + x ≤ n and w_{i+x} =  1, then s_i =  1); 
  * if both of the aforementioned conditions are false, then s_i is 0. 



You are given the integer x and the resulting string s. Reconstruct the original string w.

Input

The first line contains one integer t (1 ≤ t ≤ 1000) — the number of test cases.

Each test case consists of two lines. The first line contains the resulting string s (2 ≤ |s| ≤ 10^5, each character of s is either 0 or 1). The second line contains one integer x (1 ≤ x ≤ |s| - 1).

The total length of all strings s in the input does not exceed 10^5.

Output

For each test case, print the answer on a separate line as follows:

  * if no string w can produce the string s at the end of the process, print -1; 
  * otherwise, print the binary string w consisting of |s| characters. If there are multiple answers, print any of them. 

Example

Input


3
101110
2
01
1
110
1


Output


111011
10
-1
import java.util.*;
import java.io.*;
import java.util.Arrays;
public class Main {
 
	public static void main (String [] args) throws IOException
 
	{
		Scanner s=new Scanner(System.in);
		PrintWriter pw=new PrintWriter(System.out);
		StringBuilder sb=new StringBuilder();
 
 
		int t=s.nextInt();
		while (t-->0)
		{
 
			String y=s.next();
			int x=s.nextInt();
			char [] arr=new char[y.length()];
			for (int i=0; i<arr.length;i++)
					arr[i]='1';
 
			for (int i=0; i<arr.length;i++)
			{
				if (y.charAt(i)=='0')
				{
					if (i+x<arr.length)
						arr[i+x]='0';
 
					if (i-x>-1)
						arr[i-x]='0';
 
				}
			}
			boolean flag=true;
			for (int i=0; i<arr.length;i++)
			{
				if (y.charAt(i)=='1')
				{
					if (i+x<arr.length && arr[i+x]=='1')
						flag=true;
					else if (i-x>-1 &&arr[i-x]=='1')
						flag=true;
					else
					{
						flag=false;
						break;
					}
				}
			}
			if (!flag)
				pw.println(-1);
			else
			{
					for (char c:arr)
						pw.print(c);
					pw.println();
			}
 
 
 
 
 
		}
 
		pw.flush();
 
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
	public static void shuffle(int[] a)
	{
		int n = a.length;
		for(int i = 0; i < n; i++)
		{
			int r = i + (int)(Math.random() * (n - i));
			int tmp = a[i];
			a[i] = a[r];
			a[r] = tmp;
		}
	}
 
	/*
 
	 try {
		    Thread.sleep(2000);
		} catch(InterruptedException ex) {
		    Thread.currentThread().interrupt();
		}
 
	 */
 
 
 
	static class Scanner
{
	StringTokenizer st;
	BufferedReader br;
 
	public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}
 
	public String next() throws IOException
	{
		while (st == null || !st.hasMoreTokens())
			st = new StringTokenizer(br.readLine());
		return st.nextToken();
	}
 
	public int nextInt() throws IOException {return Integer.parseInt(next());}
 
	public long nextLong() throws IOException {return Long.parseLong(next());}
 
	public String nextLine() throws IOException {return br.readLine();}
 
	public double nextDouble() throws IOException
	{
		String x = next();
		StringBuilder sb = new StringBuilder("0");
		double res = 0, f = 1;
		boolean dec = false, neg = false;
		int start = 0;
		if(x.charAt(0) == '-')
		{
			neg = true;
			start++;
		}
		for(int i = start; i < x.length(); i++)
			if(x.charAt(i) == '.')
			{
				res = Long.parseLong(sb.toString());
				sb = new StringBuilder("0");
				dec = true;
			}
			else
			{
				sb.append(x.charAt(i));
				if(dec)
					f *= 10;
			}
		res += Long.parseLong(sb.toString()) / f;
		return res * (neg?-1:1);
	}
 
	public boolean ready() throws IOException {return br.ready();}
 
 
}
}