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.io.*;
import java.math.*;
import java.util.*;
import java.lang.*;
 
// import java.text.DecimalFormat; 
// import java.text.DecimalFormatSymbols; 
 
/*
 


*/
 
public class Main {
	
 
    public static void main(String args[] ) throws Exception {
        PrintWriter pw=new PrintWriter(System.out);
        FastScanner sc = new FastScanner();
        int T = sc.nextInt();
//        while(T-->0) {
//        	int p = sc.nextInt(), f=sc.nextInt();
//        	int cs = sc.nextInt(), cw = sc.nextInt();
//        	int s = sc.nextInt(), w = sc.nextInt();
//        	
//        }
        while(T-->0) {
        	char[] c = sc.next().toCharArray();
        	int x = sc.nextInt();
        	int n = c.length;
        	char[] a = new char[n];
        	Arrays.fill(a,'2');
        	for(int i=0;i<n;i++) {
        		if(c[i]=='0') {
        			if(i-x>=0) {
        				a[i-x]='0';
        			} 
        			if(i+x<n) {
        				a[i+x]='0';
        			}
        		}
        	}
        	boolean f = true;
        	for(int i=0;i<n;i++) {
        		if(c[i]=='1') {
        			boolean f1 = false;
        			if(i-x>=0&&a[i-x]=='2') {
        				f1 = true;
        			}
        			if(i+x<n&&a[i+x]=='2') {
        				f1 = true;
        			}
        			if(!f1) {
        				f = false;
        				break;
        			}
        		}
        	}
        	if(!f)
        		pw.println(-1);
        	else {
        		for(int i=0;i<n;i++) {
            		if(a[i]=='2') {
            			a[i] = '1';
            		}
            	}
        		pw.println(new String(a));
        	}
        }
        
        
        pw.close();
    }
    
   
    
    static <T> void deb(T x,int t){
        System.out.print(x);
        if(t==0)
        	 System.out.println();
    }
    
    
    static class FastScanner {
 		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
 		StringTokenizer st=new StringTokenizer("");
 		
 		public String next() {
 			while (!st.hasMoreElements())
 				try {
 					st=new StringTokenizer(br.readLine());
 				} catch (IOException e) {
 					e.printStackTrace();
 				}
 			return st.nextToken();
 		}
 		public String next(int k) {
 			try {
 				return br.readLine();
 			} catch (IOException e) {
 				e.printStackTrace();
 			}
 			return "Not able to read";
 		}
 		
 		int nextInt() {
 			return Integer.parseInt(next());
 		}
 		
 		long nextLong() {
 			return Long.parseLong(next());
 		}
 		
 		double nextDouble() {
 			return Double.parseDouble(next());
 		}
 		
 	    
 	}
   
}