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.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.stream.Collectors;

public class C {

    public static void main(String[] args) throws IOException {
        new C().run();
    }

    private void load_inputs(final BufferedReader br) throws IOException {
        try (
                PrintWriter pw = select_output();
        ) {
            int t = Integer.valueOf(br.readLine().trim());
            while(t-- > 0) {
                String s = br.readLine().trim();
                int x = Integer.valueOf(br.readLine().trim());
                solve(s, x, pw);
            }
        }
    }
    
    private void solve(final String s, final int x, final PrintWriter pw) {
//        System.out.println("---");
//        System.out.println("  " + s);
        boolean res = true;
        int[] w = new int[s.length()];
        Arrays.fill(w, -1);
        HashMap<Integer, Integer> variants = new HashMap<>();
                
        for(int i = 0; i < s.length(); i++) {
//            System.out.println("< " + Arrays.stream(w).mapToObj(v -> v < 0 ? "?" : Integer.toString(v)).collect(Collectors.joining()));
//            System.out.println(String.format("%-" + (i + 2) + "s^", ""));
//            System.out.println("variants: " + variants);
            int l = i - x;
            int r = i + x;
//            if(w[i] != -1) {
//                if(variants.containsKey(l)) {
//                    if(variants.get(l) == 0) {
//                        w[l] = 0;
//                    } else if(variants.get(l) == 1) {
//                        w[l] = 1;
//                    } else {
//                        w[l] = 1;
//                    }
//                    variants.remove(l);
//                }
//            }
            int ch = s.charAt(i) - '0';
            if(ch == 1) {
                if(l < 0 && r >= s.length()) {
                    res = false;
                    break;
                }
                if(l < 0) {
                    w[r] = 1;
                } 
                else if(r >= s.length()) {
                    if(w[l] == 0) {
                        res = false;
                        break;
                    }
                    w[l] = 1;
                } else {
                    if(w[l] == 0) {
                        w[r] = 1;
                    } else if(w[l] == 1) {
                        
                    } else {
                        variants.put(l, 2);
                    }
                }
            } else {
                if(l < 0 && r >= s.length()) {
                } else if(l >= 0 && r < s.length()) {
                    if(w[l] == 1) {
                        res = false;
                        break;
                    }
                    w[l] = 0;
                    w[r] = 0;
                } else if(l < 0) {
                        w[r] = 0;
                } else if(r >= s.length()) {
                    if(w[l] == 1) {
                        res = false;
                        break;
                    }
                    w[l] = 0;
                    if(variants.containsKey(l - 2 * x)) {
                        if(variants.get(l - 2 * x) == 0) {
                            res = false;
                            break;
                        }
                        if(w[l - 2 * x] == 0) {
                            res = false;
                            break;
                        }
                        w[l - 2 * x] = 1;
                        variants.remove(l - 2 * x);
                    }
                }
            }
//            System.out.println("> " + Arrays.stream(w).mapToObj(v -> v < 0 ? "?" : Integer.toString(v)).collect(Collectors.joining()));
//            System.out.println("variants: " + variants);
        }
        if(res) {
            for(int i = 0; i < s.length(); i++) {
                if(w[i] == -1/* && !variants.containsKey(i) && !variants.containsKey(i - 2 * x)*/) {
                    w[i] = 1;
                }
            }
//            System.out.println(res ? Arrays.stream(w).mapToObj(v -> v < 0 ? "?" : Integer.toString(v)).collect(Collectors.joining()) : -1);
//            variants.keySet().forEach(l -> {
////                System.out.println(v[0] + ", " + v[1] + ", " + v[2]);
//                System.out.printf("%" + (l > 0 ? "-" + l : "") + "s%d%-" + (2 * x - 1) + "s%s%n", "", variants.get(l), "", "^");
//            });
//            System.out.println(res ? Arrays.stream(w).mapToObj(v -> v < 0 ? "?" : Integer.toString(v)).collect(Collectors.joining()) : -1);
//            for(int i = 0; i < s.length(); i++) {
//                
//            }
        }
        pw.println(res ? Arrays.stream(w).mapToObj(v -> v < 0 ? "?" : Integer.toString(v)).collect(Collectors.joining()) : -1);
//        System.out.println(res ? Arrays.stream(w).mapToObj(v -> v < 0 ? "?" : Integer.toString(v)).collect(Collectors.joining()) : -1);
    }

    String nameIn = getClass().getSimpleName() + ".in";
    String nameOut = null;

    private void run() throws IOException {
        File input = null;
        if (nameIn != null && (input = new File(nameIn)).exists()) {
            try (
                    FileReader fr = new FileReader(input);
                    BufferedReader br = new BufferedReader(fr);) {
                load_inputs(br);
            }
        } else {
            try (
                    InputStreamReader fr = new InputStreamReader(System.in);
                    BufferedReader br = new BufferedReader(fr);) {
                load_inputs(br);
            }
        }
    }

    PrintWriter select_output() throws FileNotFoundException {
        if (nameOut != null) {
            return new PrintWriter(nameOut);
        }
        return new PrintWriter(System.out);
    }

}
