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


/************************************************************************
 AUTH : krishna-3249 
 DATE : 8/25/20
 TIME : 9:58 PM

 Everyone’s a whore, Grace. We just sell different parts of ourselves.
 ************************************************************************/

import java.lang.*;
import java.io.*;
import java.util.*;

public class C {

    private static final long MOD = (long) (1e9 + 7);

    private long power(long base, long exponent) {
        long res = 1;
        while (exponent > 0) {
            if ((base & 1) == 1) {
                res = (res * base) % MOD;
                exponent--;
            } else {
                res = (res * res) % MOD;
                exponent >>= 1;
            }
        }
        return res;
    }

    private long inverseMod(long number) {
        return power(number, MOD - 2);
    }

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

    private long gcd(long a, long b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    public void solve(Read input, Write output) throws Exception {
        int cases = input.readInt();
        while (cases-- > 0) {
            char[] str = input.readString().toCharArray();
            int X = input.readInt();
            int N = str.length;
            char[] res = new char[N];
            Arrays.fill(res, '1');
            for (int i=0;i<N;i++) {
                if (str[i]=='0') {
                    if (i+X<N) {
                        res[i+X] = '0';
                    }
                    if (i-X>=0) {
                        res[i-X] = '0';
                    }
                }
            }
            boolean fail = false;
            for (int i=0;i<N;i++) {
                if (str[i]=='1') {
                    if ((i-X>=0 && res[i-X]=='1')
                            || (i+X<N && res[i+X]=='1')) {
                        continue;
                    }
                    fail = true;
                }
            }
            if (fail) {
                output.printLine("-1");
            } else {
                output.printLine(new String(res));
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Read input = new Read();
        Write output = new Write();
        C D = new C();
        D.solve(input, output);
        output.flush();
        output.close();
    }

    // java fast io reader and writer
    // taken from various sources and customized

    static class Read {

        private byte[] buffer = new byte[10 * 1024];
        private int index;
        private InputStream input_stream;
        private int total;

        public Read() {
            input_stream = System.in;
        }

        public int read() throws IOException {
            if (total < 0)
                throw new InputMismatchException();
            if (index >= total) {
                index = 0;
                total = input_stream.read(buffer);
                if (total <= 0)
                    return -1;
            }
            return buffer[index++];
        }

        public long readLong() throws IOException {
            long number = 0;
            int n = read();
            while (isWhiteSpace(n))
                n = read();
            long neg = 1l;
            if (n == '-') {
                neg = -1l;
                n = read();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    number *= 10l;
                    number += (long) (n - '0');
                    n = read();
                } else throw new InputMismatchException();
            }
            return neg * number;
        }

        public int readInt() throws IOException {
            int integer = 0;
            int n = read();
            while (isWhiteSpace(n))
                n = read();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = read();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    integer *= 10;
                    integer += n - '0';
                    n = read();
                } else throw new InputMismatchException();
            }
            return neg * integer;
        }

        public double readDouble() throws IOException {
            double doub = 0;
            int n = read();
            while (isWhiteSpace(n))
                n = read();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = read();
            }
            while (!isWhiteSpace(n) && n != '.') {
                if (n >= '0' && n <= '9') {
                    doub *= 10;
                    doub += n - '0';
                    n = read();
                } else throw new InputMismatchException();
            }

            if (n == '.') {
                n = read();
                double temp = 1;
                while (!isWhiteSpace(n)) {
                    if (n >= '0' && n <= '9') {
                        temp /= 10;
                        doub += (n - '0') * temp;
                        n = read();
                    } else throw new InputMismatchException();
                }
            }
            return doub * neg;
        }

        public String readString() throws IOException {
            StringBuilder sb = new StringBuilder();
            int n = read();
            while (isWhiteSpace(n))
                n = read();
            while (!isWhiteSpace(n)) {
                sb.append((char) n);
                n = read();
            }
            return sb.toString();
        }

        public List<Double> readDoubleList(int size) throws IOException {
            List<Double> res = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                res.add(this.readDouble());
            }
            return res;
        }

        public double[] readDoubleArray(int size) throws IOException {
            double[] res = new double[size];
            for (int i = 0; i < size; i++) {
                res[i] = this.readDouble();
            }
            return res;
        }

        public List<String> readStringList(int size) throws IOException {
            List<String> res = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                res.add(this.readString());
            }
            return res;
        }

        public String[] readStringArray(int size) throws IOException {
            String[] res = new String[size];
            for (int i = 0; i < size; i++) {
                res[i] = this.readString();
            }
            return res;
        }

        public List<Integer> readIntList(int size) throws IOException {
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                res.add(this.readInt());
            }
            return res;
        }

        public List<Long> readLongList(int size) throws IOException {
            List<Long> res = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                res.add(this.readLong());
            }
            return res;
        }

        public int[] readIntArray(int size) throws IOException {
            int[] res = new int[size];
            for (int i = 0; i < size; i++) {
                res[i] = this.readInt();
            }
            return res;
        }

        public long[] readLongArray(int size) throws IOException {
            long[] res = new long[size];
            for (int i = 0; i < size; i++) {
                res[i] = this.readLong();
            }
            return res;
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1)
                return true;
            return false;
        }
    }

    static class Write {

        private final BufferedWriter bw;

        public Write() {
            bw = new BufferedWriter(new OutputStreamWriter(System.out));
        }

        public void print(Object str) throws IOException {
            bw.append(str + "");
        }

        public void printLine(Object str) throws IOException {
            print(str);
            bw.append("\n");
        }

        public void close() throws IOException {
            bw.close();
        }

        public void flush() throws IOException {
            bw.flush();
        }
    }
}