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.*;
public class Main {

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        for (int test = 1; test <= T; test++) {
            char[] input = br.readLine().toCharArray();
            int X = Integer.parseInt(br.readLine());
            int len = input.length;
            int[] check = new int[len];
            Arrays.fill(check, -1);
            for (int i = 0; i < len; i++) {
                if (input[i] == '0') {
                    if (i - X >= 0) check[i - X] = 0;
                    if (i + X < len) check[i + X] = 0;
                }
            }
            boolean hasAnswer = true;

            for (int i = 0; i < len; i++) {
                if (input[i] == '1') {
                    if (i - X >= 0 && check[i - X] != 0) continue;
                    if (i + X < len && check[i + X] != 0) continue;
                    hasAnswer = false;
                    break;
                }
            }
            if (hasAnswer) {
                for (int i = 0; i < len; i++) {
                    if (check[i] == 0) System.out.print('0');
                    else System.out.print('1');
                }
                System.out.println();
            } else {
                System.out.println("-1");
            }


        }
    }

    private static class FastIO {
        private static final int DEFAULT_BUFFER_SIZE = 65536;
        private static final int DEFAULT_LONG_SIZE = 20;
        private static final int DEFAULT_INT_SIZE = 11;
        private static final int DEFAULT_LINE_SIZE = 30;
        private static final int EOF = -1;

        private static final byte ASCII_n = 10;
        private static final byte ASCII_r = 13;
        private static final byte ASCII_space = 32;
        private static final byte ASCII_minus = 45;
        private static final byte ASCII_0 = 48;
        private static final byte ASCII_9 = 57;

        private final DataInputStream din;
        private final DataOutputStream dout;

        private byte[] inbuffer;
        private int inbufferpointer, bytesread;
        private byte[] outbuffer;
        private int outbufferpointer;

        private byte[] bytebuffer;
        private char[] charbuffer;

        private FastIO(int inbuffersize, int outbuffersize) {
            this.din = new DataInputStream(System.in);
            this.dout = new DataOutputStream(System.out);

            this.inbuffer = new byte[inbuffersize];
            this.inbufferpointer = 0;
            this.bytesread = 0;
            this.outbuffer = new byte[outbuffersize];
            this.outbufferpointer = 0;

            this.bytebuffer = new byte[DEFAULT_LONG_SIZE];
            this.charbuffer = new char[DEFAULT_LINE_SIZE];
        }

        private FastIO() {
            this(DEFAULT_BUFFER_SIZE, DEFAULT_BUFFER_SIZE);
        }

        private FastIO(int buffersize) {
            this(buffersize, buffersize);
        }

        private byte read() {
            if (inbufferpointer == bytesread)
                fillbuffer();
            return bytesread == EOF ? EOF : inbuffer[inbufferpointer++];
        }

        private void fillbuffer() {
            try {
                bytesread = din.read(inbuffer, inbufferpointer = 0, inbuffer.length);
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }

        private void write(byte b) {
            if (outbufferpointer == outbuffer.length)
                flushbuffer();
            outbuffer[outbufferpointer++] = b;
        }

        private void flushbuffer() {
            if (outbufferpointer != 0) {
                try {
                    dout.write(outbuffer, 0, outbufferpointer);
                } catch (Exception e) {
                    throw new RuntimeException(e);
                }
                outbufferpointer = 0;
            }
        }

        private char nextChar() {
            byte b;
            while (isSpace(b = read()))
                ;
            return (char) b;
        }

        private String next() {
            byte b;
            while (isSpace(b = read())) {
            }
            int index = 0;
            do {
                charbuffer[index++] = (char) b;
            } while (!isSpace(b = read()));
            return new String(charbuffer, 0, index);
        }

        private String nextLine() {
            byte b;
            int index = 0;
            while (!isLine(b = read()))
                charbuffer[index++] = (char) b;
            return new String(charbuffer, 0, index);
        }

        private int nextInt() {
            byte b;
            while(isSpace(b = read()))
                ;
            boolean negative = false;
            if (b == '-') {
                negative = true;
                b = read();
            }
            int result = b - '0';
            while (isDigit(b = read()))
                result = result * 10 + b - '0';
            return negative ? -result : result;
        }

        private long nextLong() {
            byte b;
            while(isSpace(b = read()))
                ;
            boolean negative = false;
            if (b == '-') {
                negative = true;
                b = read();
            }
            long result = b - '0';
            while (isDigit(b = read()))
                result = result * 10 + b - '0';
            return negative ? -result : result;
        }

        private float nextFloat() {
            byte b;
            while (isSpace(b = read()))
                ;
            boolean negative = false;
            if (b == ASCII_minus) {
                negative = true;
                b = read();
            }
            float f = 0;
            do {
                f = f * 10 + b - ASCII_0;
            } while (isDigit(b = read()));
            int d = 1;
            b = read();
            do {
                f = f * 10 + b - ASCII_0;
                d = d * 10;
            } while (isDigit(b = read()));
            return f / d;

        }

        private void print(char c) {
            write((byte) c);
        }

        private void print(char[] c) {
            for (int i = 0; i < c.length; i++) {
                write((byte) c[i]);
            }
        }

        private void print(String s) {
            for (int i = 0; i < s.length(); i++) {
                write((byte) s.charAt(i));
            }
        }

        private void print(int i) {
            if (i == 0) {
                write(ASCII_0);
            } else {
                if (i < 0) {
                    write(ASCII_minus);
                    i = -i;
                }
                int index = 0;
                while (i > 0) {
                    bytebuffer[index++] = (byte) ((i % 10) + ASCII_0);
                    i /= 10;
                }
                while (index-- > 0) {
                    write(bytebuffer[index]);
                }
            }
        }

        private void print(long l) {
            if (l == 0) {
                write(ASCII_0);
            } else {
                if (l < 0) {
                    write(ASCII_minus);
                    l = -l;
                }
                int index = 0;
                while (l > 0) {
                    bytebuffer[index++] = (byte) ((l % 10) + ASCII_0);
                    l /= 10;
                }
                while (index-- > 0) {
                    write(bytebuffer[index]);
                }
            }
        }

        private boolean isLine(byte b) {
            return b == ASCII_r || b == ASCII_n || b == EOF;
        }

        private boolean isSpace(byte b) {
            return b <= ASCII_space && b >= 0;
        }

        private boolean isDigit(byte b) {
            return b >= ASCII_0 && b <= ASCII_9;
        }
    }
}