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.*;

/*
Shortcut Commands

makeali  : Make ArrayList of Integer
makesti : Make Stack of Integer
makeqi : Make Queue of Integer
makepqi : Make PriorityQueue of Integer

makestc : Make Stack of Character

mapii : Make Map<Integer,Integer>
mappi : Make Map<Pair,Integer>

print
println
printf

*/

public class C{

    public static boolean verify(String s,String r,int x){
        int len = s.length();
        for(int i=0;i<x && i+x<len;i++){
            if(r.charAt(i)!=s.charAt(i+x))
            return false;
        }

        for(int i=x;i<len-x;i++){
            if(r.charAt(i)=='0'){
                if(s.charAt(i-x)=='1' || s.charAt(i+x)=='1')
                return false;
            }else{
                if(s.charAt(i-x)=='0' && s.charAt(i+x)=='0')
                return false;
            }
        }

        for(int i=len-x;i<len;i++){
            if((i-x)>=0 && r.charAt(i)!=s.charAt(i-x))
            return false;
        }

        return true;
    }

	public static void solve()throws IOException{
        char[] r = sc.next().toCharArray();
        int x = sc.nextInt();
        int n = r.length;
        char[] s = new char[n];
        Arrays.fill(s,'1');
        
        for(int i=0;i<n;i++){
            if(r[i]=='0'){
                if(i-x>=0) s[i-x]='0';
                if(i+x<n) s[i+x]='0';
            }
        }

        boolean verify = true;

        for(int i=0;i<n;i++){
            if(r[i]=='1'){
                if(i-x>=0 && s[i-x]=='1')continue;
                if(i+x<n && s[i+x]=='1')continue;
                verify=false;
                break;
            }
        }

        if(verify){
            for(int i=0;i<n;i++)
            System.out.print(s[i]);
        }else{
            System.out.print("-1");
        }
	}

	public static void main(String args[])throws IOException{
		int t = sc.nextInt();
		for(int i=1;i<=t;i++){
			solve();
			System.out.println();
		}
    }
    
    public static void sort(int[] arr,boolean reverse){
        ArrayList<Integer> list = new ArrayList<Integer>();
        int n =arr.length;
        for(int i=0;i<n;i++){
            list.add(arr[i]);
        }

        if(reverse)
        Collections.sort(list,Collections.reverseOrder());
        else
        Collections.sort(list);

        for(int i=0;i<n;i++){
            arr[i] = list.get(i);
        }
    }

    static class Graph{
        int n;
        ArrayList<Integer>[] g;

        Graph(int n){
            this.n = n;
            this.g = new ArrayList[n];
            for(int i=0;i<n;i++){
                this.g[i] = new ArrayList<Integer>();
            }
        }

        // ArrayList<Integer> get(int i){
		// 	return this.g.get(i);
		// }

        void add(int a,int b){
            this.g[a].add(b);
        }
    }

    static class Pair{

        // Implementing equals() and hashCode()
        // Map<Pair, V> map = //...

        private final int x;
        private final int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Pair)) return false;
            Pair pair = (Pair) o;
            return x == pair.x && y == pair.y;
        }

        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + y;
            return result;
        }
    }

	static FastScanner sc = new FastScanner();

	static class FastScanner {
			BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer st=new StringTokenizer("");
			String next() {
				while (!st.hasMoreTokens())
					try {
						st=new StringTokenizer(br.readLine());
					} catch (IOException e) {
						e.printStackTrace();
					}
				return st.nextToken();
			}
			
			int nextInt() {
				return Integer.parseInt(next());
			}
			int[] readArray(int n) {
				int[] a=new int[n];
				for (int i=0; i<n; i++) a[i]=nextInt();
				return a;
			}
			long nextLong() {
				return Long.parseLong(next());
			}
			public long[] readLongArray(int n) {
				long[] a=new long[n];
				for (int i=0; i<n; i++) a[i]=nextLong();
				return a;
			}
	}
}