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.math.*;
	import java.awt.geom.*;
	 
	import static java.lang.Math.*;
	 
	 public class Solution implements Runnable {
		
		 int mod1=(int)1e9+7;
		 int mod2=998244353;
	     
		 public void solve() throws Exception {
			 int t=sc.nextInt();
			 while(t-->0)
			 {
//				 int n=sc.nextInt();
//				 int m=sc.nextInt();
//				 int p=sc.nextInt();
//				 int q=sc.nextInt();
//				 int w1=sc.nextInt();
//				 int w2=sc.nextInt();
				 String s=sc.nextToken();
				 int x=sc.nextInt();
				 int len=s.length();
				 int count=0;
				// String result="";
				 char arr[]=s.toCharArray();
				 char result[]=new char[len];
				 boolean flag=true;
				 for(int i=0;i<len;i++)
					 result[i]=' ';
				 for(int i=0;i<len;i++)
				 {
					 if(s.charAt(i)=='1')
					 {
						 if(i-x>=0)
						 {
							 if(result[i-x]==' ' || result[i-x]=='1')
							 {
								 result[i-x]='1';
							 }
							 else 
							 {
								 if(i+x<len)
								 {
									 result[i+x]='1';
								 }
								 else {
									 flag=false;
									 break;
								 }
							 }
						 }
						 else
						 {
							 if(i+x<len)
							 {
								 result[i+x]='1';
							 }
							 else {
								 flag=false;
								 break;
							 }
						 }
					 }
					 else
					 {
						 if(i-x<0 && i+x>=len)
						 {
							 continue;
						 }
						 if(i-x>=0)
						 {
							 if(result[i-x]=='1')
							 {
								 flag=false;
								 break;
							 }
							 else result[i-x]='0';
						 }
						 if(i+x<len)
							 result[i+x]='0';
						 
					 }
				
			    }
				 if(!flag)
				 {
					 out.println(-1);
					 continue;
				 }
				 for(int i=0;i<len;i++)
				 {
					 if(result[i]==' ')
						 out.print("0");
					 else
					 out.print(result[i]);
				 }
				out.println();
				
				
		 }
		 }
				
		 
	    
	    static long power(long x, long y, long p) 
	    { 
	        long res = 1;      
	       
	        x = x % p;  
	       if (x == 0) return 0;    
	  
	        while (y > 0) 
	        { 
	            if((y & 1)==1) 
	                res = (res * x) % p; 
	            y = y >> 1;  
	            x = (x * x) % p;  
	        } 
	        return res; 
	    } 
	    
	    		
	    
	    
	    
	    
	    
	    static Throwable uncaught;
	 
	    BufferedReader in;
	    FastScanner sc;
	    PrintWriter out;
	 
	    @Override
	    public void run() {
	        try {
	            in = new BufferedReader(new InputStreamReader(System.in));
	            out = new PrintWriter(System.out);
	            sc = new FastScanner(in);
	            solve();
	        } catch (Throwable uncaught) {
	            Solution.uncaught = uncaught;
	        } finally {
	            out.close();
	        }
	    }
	 
	    public static void main(String[] args) throws Throwable {
	        Thread thread = new Thread(null, new Solution(), "", (1 << 26));
	        thread.start();
	        thread.join();
	        if (Solution.uncaught != null) {
	            throw Solution.uncaught;
	        }
	    }
	 
	}
	 
	class FastScanner {
	 
	    BufferedReader in;
	    StringTokenizer st;
	 
	    public FastScanner(BufferedReader in) {
	        this.in = in;
	    }
	 
	    public String nextToken() throws Exception {
	        while (st == null || !st.hasMoreTokens()) {
	            st = new StringTokenizer(in.readLine());
	        }
	        return st.nextToken();
	    }
	 
	    public int nextInt() throws Exception {
	        return Integer.parseInt(nextToken());
	    }
	    
	    public int[] readArray(int n) throws Exception {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
	 
	    public long nextLong() throws Exception {
	        return Long.parseLong(nextToken());
	    }
	 
	    public double nextDouble() throws Exception {
	        return Double.parseDouble(nextToken());
	    }
	 
	}