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
// template halnix16


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {


    static BufferedReader br;

    public static void main(String[] args) throws Exception {
        // write your code here
        br = new BufferedReader(new InputStreamReader(System.in));

        int t = (int) in();
        while (t-- > 0) {

            String s = sin();
            int n = s.length();
            int x = integer();
            int ans[] = new int[s.length()];boolean visted[] = new boolean[n];
            Arrays.fill(ans, -1);

            for(int i =0;i<n;i++){

                if(s.charAt(i)=='0'){

                    if(i+x<n){
             //           System.out.println("fillling "+(i+x));
                        ans[i+x]=0;
                    }
                    if(i-x>=0){
               //         System.out.println("fii "+(i-x));
                        ans[i-x]=0;
                    }

                }
            }
            boolean is = true;
            for(int i =0;i<n;i++){


                if(s.charAt(i)=='1'){
                    boolean poss = false;

                    if(i+x<n){

              //          System.out.println(i+" "+(i+x)+" "+" "+ans[i+x]);
                        if(ans[i+x]!=0){
                            ans[i+x]=1;
                            poss=true;
                        }
                    }
                    if(i-x>=0){
                  //      System.out.println(i+" "+(i-x)+" "+ans[i-x]);
                        if(ans[i-x]!=0){
                            ans[i-x]=1;
                            poss=true;
                        }
                    }
                    if(!poss){
                      //  System.out.println("fail ");
                        is=false;
                        break;
                    }
                }
            }
            if(!is){
                System.out.println(-1);
                continue;
            }StringBuilder sb = new StringBuilder();
            for(int i =0;i<n;i++){
                if(ans[i]==-1){
                    sb.append(1);
                }else
                sb.append(ans[i]);
            }
            System.out.println(sb.toString());
        }
    }


    static long[] arr(long n) throws Exception {

        String read[] = sarrin();
        long arr[] = new long[(int) n];
        for (int k = 0; k < n; k++)
            arr[k] = in(read[k]);
        return arr;

    }

    static long[][] arr(long n, long m) throws Exception {


        long arr[][] = new long[(int) n][(int) m];
        for (int k = 0; k < n; k++) {
            String read[] = sarrin();
            for (int j = 0; j < m; j++)
                arr[k][j] = in(read[k]);
        }
        return arr;

    }

    static long in() throws Exception {
        return Long.parseLong(br.readLine());


    }

    static long in(String num) throws Exception {
        return Long.parseLong(num);


    }


    static String sin() throws Exception {

        return br.readLine();
    }

    static String[] sarrin() throws Exception {

        return br.readLine().split(" ");

    }

    static String[] regexSplit() throws Exception {
        return br.readLine().split(" ?(?<!\\G)((?<=[^\\p{Punct}])(?=\\p{Punct})|\\b) ?");
    }

    static int integer() throws Exception {
        return Integer.parseInt(br.readLine());
    }


}






