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
// package com.company;
import java.util.*;
import java.lang.*;
import java.io.*;
//****Use Integer Wrapper Class for Arrays.sort()****
public class EX3 {
    static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] Args)throws Exception{
        FastReader scan=new FastReader(System.in);
        int t=1;
        t=scan.nextInt();
        while(t-->0){
            String s=scan.next();
            int x=scan.nextInt();
            StringBuilder ans=new StringBuilder();
            for(int i=0;i<s.length();i++){
                ans.append("2");
            }
            int n=s.length();
            boolean pos=true;
            for(int i=0;i<x;i++){
                if(s.charAt(i)=='1'){
                    if(i+x<n){
                        ans.setCharAt(i+x,'1');
                    }else{
                        pos=false;
                        break;
                    }
                }else{
                    if(i+x<n){
                        ans.setCharAt(i+x,'0');
                    }
                }
            }
            for(int i=0;i<x;i++){
                int in=n-1-i;
                if(s.charAt(in)=='1'){
                    if(in-x>=0){
                        if(ans.charAt(in-x)!='0'){
                            ans.setCharAt(in-x,'1');
                        }else{
                            pos=false;
                            break;
                        }
                    }else{
                        pos=false;
                        break;
                    }
                }else{
                    if(in-x>=0){
                        if(ans.charAt(in-x)!='1'){
                            ans.setCharAt(in-x,'0');
                        }else{
                            pos=false;
                            break;
                        }
                    }
                }
            }
            for(int i=x;i<n-x;i++){
                if(s.charAt(i)=='1'){
                    char l=ans.charAt(i-x);
                    char r=ans.charAt(i+x);
                    if(l=='0'&&r=='0'){
                        pos=false;
                        break;
                    }else{
                        if(l!='0'){
                            ans.setCharAt(i-x,'1');
                        }else{
                            ans.setCharAt(i+x,'1');
                        }
                    }
                }else{
                    char l=ans.charAt(i-x);
                    char r=ans.charAt(i+x);
                    if(l=='1'||r=='1'){
                        pos=false;
                        break;
                    }else{
                        ans.setCharAt(i-x,'0');
                        ans.setCharAt(i+x,'0');
                    }
                }
            }
            if(pos){
                for(int i=0;i<n;i++){
                    if(ans.charAt(i)=='2'){
                        ans.setCharAt(i,'1');
                    }
                }
                out.println(ans);
            }else{
                out.println(-1);
            }
        }
        out.flush();
        out.close();
    }
    static class FastReader {

        byte[] buf = new byte[2048];
        int index, total;
        InputStream in;

        FastReader(InputStream is) {
            in = is;
        }

        int scan() throws IOException {
            if (index >= total) {
                index = 0;
                total = in.read(buf);
                if (total <= 0) {
                    return -1;
                }
            }
            return buf[index++];
        }

        String next() throws IOException {
            int c;
            for (c = scan(); c <= 32; c = scan()) ;
            StringBuilder sb = new StringBuilder();
            for (; c > 32; c = scan()) {
                sb.append((char) c);
            }
            return sb.toString();
        }

        int nextInt() throws IOException {
            int c, val = 0;
            for (c = scan(); c <= 32; c = scan()) ;
            boolean neg = c == '-';
            if (c == '-' || c == '+') {
                c = scan();
            }
            for (; c >= '0' && c <= '9'; c = scan()) {
                val = (val << 3) + (val << 1) + (c & 15);
            }
            return neg ? -val : val;
        }
        long nextLong() throws IOException {
            int c;
            long val = 0;
            for (c = scan(); c <= 32; c = scan()) ;
            boolean neg = c == '-';
            if (c == '-' || c == '+') {
                c = scan();
            }
            for (; c >= '0' && c <= '9'; c = scan()) {
                val = (val << 3) + (val << 1) + (c & 15);
            }
            return neg ? -val : val;
        }
    }
}
