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

    import static java.lang.Math.*;

    public class Main implements Runnable
    {
        static class InputReader
        {
            private InputStream stream;
            private byte[] buf = new byte[1024];
            private int curChar;
            private int numChars;
            private SpaceCharFilter filter;
            private BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

            public InputReader(InputStream stream)
            {
                this.stream = stream;
            }

            public int read()
            {
                if (numChars==-1)
                    throw new InputMismatchException();

                if (curChar >= numChars)
                {
                    curChar = 0;
                    try
                    {
                        numChars = stream.read(buf);
                    }
                    catch (IOException e)
                    {
                        throw new InputMismatchException();
                    }

                    if(numChars <= 0)
                        return -1;
                }
                return buf[curChar++];
            }

            public String nextLine()
            {
                String str = "";
                try
                {
                    str = br.readLine();
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
                return str;
            }
            public int nextInt()
            {
                int c = read();

                while(isSpaceChar(c))
                    c = read();

                int sgn = 1;

                if (c == '-')
                {
                    sgn = -1;
                    c = read();
                }

                int res = 0;
                do
                {
                    if(c<'0'||c>'9')
                        throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = read();
                }
                while (!isSpaceChar(c));

                return res * sgn;
            }

            public long nextLong()
            {
                int c = read();
                while (isSpaceChar(c))
                    c = read();
                int sgn = 1;
                if (c == '-')
                {
                    sgn = -1;
                    c = read();
                }
                long res = 0;

                do
                {
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = read();
                }
                while (!isSpaceChar(c));
                    return res * sgn;
            }

            public double nextDouble()
            {
                int c = read();
                while (isSpaceChar(c))
                    c = read();
                int sgn = 1;
                if (c == '-')
                {
                    sgn = -1;
                    c = read();
                }
                double res = 0;
                while (!isSpaceChar(c) && c != '.')
                {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = read();
                }
                if (c == '.')
                {
                    c = read();
                    double m = 1;
                    while (!isSpaceChar(c))
                    {
                        if (c == 'e' || c == 'E')
                            return res * Math.pow(10, nextInt());
                        if (c < '0' || c > '9')
                            throw new InputMismatchException();
                        m /= 10;
                        res += (c - '0') * m;
                        c = read();
                    }
                }
                return res * sgn;
            }

            public String readString()
            {
                int c = read();
                while (isSpaceChar(c))
                    c = read();
                StringBuilder res = new StringBuilder();
                do
                {
                    res.appendCodePoint(c);
                    c = read();
                }
                while (!isSpaceChar(c));

                return res.toString();
            }

            public boolean isSpaceChar(int c)
            {
                if (filter != null)
                    return filter.isSpaceChar(c);
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
            }

            public String next()
            {
                return readString();
            }

            public interface SpaceCharFilter
            {
                public boolean isSpaceChar(int ch);
            }
        }


        public static void main(String args[]) throws Exception
        {
            new Thread(null, new Main(),"Main",1<<26).start();
        }
        //User-defined functions goes here...
        class pair{
            int x, y;
            pair(int x, int y){
                this.x = x;
                this.y = y;
            }
        }

      
        void swap(int[] a, int pos1, int pos2){
            int temp = a[pos1];
            a[pos1] = a[pos2];
            a[pos2] = temp;
        }


        boolean powerof2(int n){
            return ((n > 2) && ((n & (n-1)) == 0));
        }


        void bfs(int st, int[] dist){
            Queue<Integer> q = new LinkedList<>();
            dist[st] = 0;
            q.add(st);

            while(q.size()>0){
                int temp = q.poll();
                for (int i: graph[temp]) {
                    if(dist[i] == Integer.MAX_VALUE){
                        q.add(i);
                        dist[i] = dist[temp] + 1;
                    }
                }
            }
        }

        ArrayList<Integer>[] graph;
        public void run()
        {
            InputReader sc= new InputReader(System.in);
            PrintWriter ww= new PrintWriter(System.out);

            //Your code goes here...
            int test = sc.nextInt();
            for (int q0=0; q0<test; q0++) {
                String s = sc.next();
                int n = s.length();

                int x = sc.nextInt();
                int  w[] = new int[n];
                Arrays.fill(w, 1);

                for (int i=0; i<n; i++) {
                    if(s.charAt(i) == '0'){
                        if(i-x >= 0)
                            w[i-x] = 0;
                        if(i+x <= n-1)
                            w[i+x] = 0;
                    }

                }

                String teststr = "";
                String ans = "";
                
                for (int i=0; i<n; i++) {
                    if((i-x >= 0 && w[i-x] == 1) || (i+x <= n-1 && w[i+x] == 1)){
                        teststr += '1';
                    }
                    else
                        teststr += '0';


                    ans += (char)(w[i] + 48);
                }
                
                if(teststr.equals(s)){
                    ww.println(ans);
                }   
                else
                    ww.println("-1");

            }

            ww.close();
        }
    }