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 Pc{
	public static void main(String[] args) throws IOException{
		FastReader sc = new FastReader();
		BufferedWriter out = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(java.io.FileDescriptor.out),"ASCII"),512);
		int t = sc.nextInt();
		while(t-- > 0){
			char[] ch = sc.nextLine().toCharArray();
			int n = ch.length;
			int x = sc.nextInt();
			char[] op = new char[n];
			Arrays.fill(op, 'a');
			int temp = 1;
			for(int i=0;i<n;i++){
				int a = i-x;
				int b = i+x;
				if(ch[i] == '0'){
					if(a >= 0){
						if(op[a] == '1'){
							temp = 0;
							break;
						}else op[a] = '0';
					}
					if(b < n) op[b] = '0';
				}else{
					if(a >= 0){
						if(op[a] == '0'){
							if(b < n) op[b] = '1';
							else{
								temp = 0;
								break;
							}
						}else op[a] = '1';
					}else if(b < n) op[b] = '1';
					else{
						temp = 0;
						break;
					}
				}
			}
			if(temp == 0) out.write(-1 + "");
			else for(int i=0;i<n;i++){
				if(op[i] == 'a') op[i] = '0';
				out.write(op[i] + "");
			}
			out.write('\n');
		}
		out.flush();
	}
}
class FastReader{
	BufferedReader br;
	StringTokenizer st;
	public FastReader(){
		br = new BufferedReader(new InputStreamReader(System.in));
	}
	String next(){
		while(st == null || !st.hasMoreElements()){
			try{ 
				st = new StringTokenizer(br.readLine()); 
			} 
			catch (IOException  e){ 
				e.printStackTrace(); 
			} 
		} 
		return st.nextToken();
	}
	int nextInt(){ 
        return Integer.parseInt(next()); 
	}
    long nextLong(){ 
        return Long.parseLong(next()); 
    }
    double nextDouble(){ 
        return Double.parseDouble(next()); 
    }
    String nextLine(){ 
        String str = ""; 
        try{ 
            str = br.readLine(); 
        } 
		catch (IOException e){ 
            e.printStackTrace(); 
        } 
        return str; 
    }
}