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.util.*;
import java.math.*;

 
public class Main
{
	 /*static class Pair implements Comparable<Pair>{
       int index,value;
       Pair(int a,int b){
           index=a;value=b;
       }
       public int compareTo(Pair a){
           if(this.value==a.value)
           return this.index-a.index;
           return this.value-a.value;
       }
   }*/
	 /*static void seive(int p[]){
       for (int i = 2; i <100001;i++) { 
           if(p[i]==0){
            for(int j=i;j<100001;j=j+i){
                if(p[j]==0)
                p[j]=i;
            }}
        }
   }*/
    
	
     public static void main(String[] args) {
	   FastReader s=new FastReader();
	   int t=s.nextInt();
	  
	   for(int f1=0;f1<t;f1++){
	      String a=s.next();
	      int x=s.nextInt();
	      int n=a.length();
	      int w[]=new int[n+1];
	      for(int i=0;i<=n;i++){
	          w[i]=1;
	      }
	      int d=0;
	     /* for(int i=1;i<=n;i++){
	          int j=i;
	          if(i-x<1 || j+x>n){
	              if(i-x<1){
	                  if(j+x>n)continue;
	                  if(w[j+x]==-1){
	                      w[j+x]=a.charAt(i-1)-'0';
	                  }
	                  else {
	                      if(w[j+x]!=a.charAt(i-1)-'0')
	                      d=1;
	                  }
	              }
	              else if(j+x>n){
	                  if(i-x<1)continue;
	                  if(w[i-x]==-1){
	                      w[i-x]=a.charAt(i-1)-'0';
	                  }
	                  else {
	                      if(w[i-x]!=a.charAt(i-1)-'0')
	                      d=1;
	                  }
	              }
	          }
	      }*/
	     /* for(int i=1;i<=n;i++){int j=i;
	          if(i-x>=1 && j+x<=n){
	              int k=i-2*x;int l=i+2*x;
	              if(k<1 && l>n)
	              continue;
	              if(k>=1 && l<=n){
	                 continue;
	              }
	              else if(k>=1){
	                  if(a.charAt(i-1)==0){
	                      if(w[k]==1){
	                          d=1;
	                      }
	                      w[k]=0;
	                  }
	                  else{
	                      if(w[k]==0){
	                          d=1;
	                      }
	                      w[k]=1;
	                  }
	              }
	              else if(l<=n){
	                   if(a.charAt(i-1)==0){
	                      if(w[l]==1){
	                          d=1;
	                      }
	                      w[l]=0;
	                  }
	                  else{
	                      if(w[l]==0){
	                          d=1;
	                      }
	                      w[l]=1;
	                  }
	              }
	              
	          }
	      }*/
	      for(int i=1;i<=n;i++){
	          if(a.charAt(i-1)=='0'){
	              if(i+x<=n){
	              w[i+x]=0;}
	               if(i-x>=1){
	              w[i-x]=0;}
	          }
	      }
	      for(int i=1;i<=n;i++){
	          if(a.charAt(i-1)=='1'){
	              if(i+x<=n && i-x>=1){
	                  if(w[i+x]==0 && w[i-x]==0){
	                      d=1;
	                  }
	                  
	              }
	              else if(i+x<=n){
	                  if(w[i+x]==0){
	                      d=1;
	                  }
	                 
	              }
	              else if(i-x>=1){
	                  if(w[i-x]==0){
	                      d=1;
	                  }
	              }
	              else d=1;
	          }
	      }
	      if(d==1){
	          System.out.println("-1");
	          continue;
	      }
	     /* for(int i=1;i<=n;i++){
	          if(w[i]==-1){
	              if(i+x<=n){
	                  w[i]=a.charAt(i+x-1)-'0';
	              }
	              else if(i-x>=1){
	                  w[i]=a.charAt(i-x-1)-'0';
	              }
	              else w[i]=1;
	          }
	      }*/
	      StringBuilder sbr=new StringBuilder("");
	      for(int i=1;i<=n;i++){
	          sbr.append(w[i]);
	      }
	      System.out.println(sbr);
	      
	   }
    }
	
	
	
	
	
	
	
	
	
	
	
	
	
	
    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader()
        {
            br = new BufferedReader(new
                     InputStreamReader(System.in));
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt()
        {
            return Integer.parseInt(next());
        }
 
        long nextLong()
        {
            return Long.parseLong(next());
        }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
 
   
}
        