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 static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.Double.parseDouble;
import static java.lang.Math.PI;
import static java.lang.Math.min;
import static java.lang.System.arraycopy;
import static java.lang.System.exit;
import static java.util.Arrays.copyOf;

import java.util.LinkedList;
import java.util.Iterator;
import java.io.FileReader;
import java.io.FileWriter;
import java.math.BigInteger; 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.Comparator;
import java.lang.StringBuilder;
import java.util.Collections;
public class Solution {

	static int scanInt() throws IOException {
		return parseInt(scanString());
	}

	static long scanLong() throws IOException {
		return parseLong(scanString());
	}
	static double scanDouble() throws IOException {
		return parseDouble(scanString());
	}

	static String scanString() throws IOException {
		if (tok == null || !tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine());
		}
		return tok.nextToken();
	}
	static String scanLine() throws IOException {
		return in.readLine();
	}


	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer tok;
	static int spf[];
	public static void main(String[] args) {
		try {
			long startTime = System.currentTimeMillis();

			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			//in = new BufferedReader(new FileReader("input.txt"));
			//out = new PrintWriter(new FileWriter("output.txt"));
			
			
			solve();
			
			long endTime   = System.currentTimeMillis();
			long totalTime = endTime - startTime;
			//System.out.println(totalTime+"  "+System.currentTimeMillis() );
			in.close();
			out.close();
			
		} catch (Throwable e) {
			e.printStackTrace();
			exit(1);
		}
	}
	private static void solve() throws IOException{
		int test=scanInt();
		
		while(--test>-1){
			char str[]=scanString().toCharArray();
			char res[]=new char[str.length];
			int x=scanInt();
			for(int i=0; i<res.length;++i){
				res[i]='1';
			}
			
			
			boolean flag=false;
			
			for(int i=0; i<str.length;++i){
				char ch=str[i];
				if(ch=='0'){
					if(i-x>=0){
						res[i-x]='0';
					}
					if(i+x<str.length){
						res[i+x]='0';
					}
				}
			}
			for(int i=0; i<str.length; ++i){
				char ch=str[i];
				if(ch=='1'){
					if(i-x>=0){
						if(res[i-x]=='1')
							continue;
					}
					if(i+x<res.length){
						if(res[i+x]=='1'){
							continue;
						}
					
					}
					
						flag=true;
						break;
					
				}
				else{
					if(i-x>=0 && res[i-x]=='1'){
						flag=true;
						break;
					}
					if(i+x<res.length && res[i+x]=='1'){
						flag=true;
						break;
					}
				}
			}
			if(flag){
				out.println(-1);
				continue;
			}
			out.println(res);
			
		}
		
		
		
		
	} 
	

	

	
	
	
}
 

