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.lang.*;
import java.io.*;

public final class binary_string_reconstruction{
    public static void main(String[] args) throws java.lang.Exception{
        Reader r = new Reader();
        r.init(System.in);
        int t = r.nextInt();
        while(t-->0){
            String s = r.next();
            int x = r.nextInt();
            int n = s.length();
            char[] st = new char[n];
            char[] w = new char[n];
            boolean flag = false;
            for(int i=0;i<n;i++) w[i] = '1';
            for(int i=0;i<n;i++) st[i] = s.charAt(i);
            for(int i=0;i<n;i++){
                if(st[i]=='0'){
                    if(i-x>-1) w[i-x]='0';
                    if(i+x<n) w[i+x] ='0'; 
                }
            }

            for(int i=0;i<n;i++){
                if(i-x>-1 && w[i-x]=='1') st[i] = '1';
                else if(i+x<n && w[i+x]=='1') st[i] = '1';
                else st[i]='0';
            }
            for(int i=0;i<n;i++){
                if(st[i] != s.charAt(i)){
                    flag = true;
                    break;
                }
            }

            if(flag) 
                System.out.println("-1");
            else System.out.println(new String(w));
        }

    
    }

    static int gcd(int a, int b){
        if(a==0) return b;
        return gcd(b%a, a);
    }

    /** Class for buffered reading int and double values */
    static class Reader {
        static BufferedReader reader;
        static StringTokenizer tokenizer;
    
        /** call this method to initialize reader for InputStream */
        static void init(InputStream input) {
            reader = new BufferedReader(
                        new InputStreamReader(input) );
            tokenizer = new StringTokenizer("");
        }
    
        /** get next word */
        static String next() throws IOException {
            while ( ! tokenizer.hasMoreTokens() ) {
                //TODO add check for eof if necessary
                tokenizer = new StringTokenizer(
                    reader.readLine() );
            }
            return tokenizer.nextToken();
        }
    
        static int nextInt() throws IOException {
            return Integer.parseInt( next() );
        }
    
        static double nextDouble() throws IOException {
            return Double.parseDouble( next() );
        }
    }
}