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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		Reader reader = new Reader(System.in);
		PrintWriter print = new PrintWriter(System.out);
		Solver solver = new Solver();
		solver.solve(reader, print);

		print.close();
	}

	static class Solver {
		public void solve(Reader reader, PrintWriter print) throws IOException {
			int __; __ = reader.nextInt();
			while (__-- > 0) {
				String s = reader.next();
				int x; x = reader.nextInt();
				boolean f = false;
				int[] w = new int [s.length() + 5];
				Arrays.fill(w, -1);
				for (int i = 0; i < s.length(); ++i) {
					if (i + x >= s.length() && i - x < 0 && s.charAt(i) == '1') { f = true; break; }
					else if (i + x < s.length() && i - x >= 0) {
						if (w[i - x] == -1) {
							if (s.charAt(i) == '0') w[i + x] = w[i - x] = s.charAt(i) - '0';
							else w[i - x] = s.charAt(i) - '0';
						}
						else if (w[i - x] != s.charAt(i) - '0') {
							if (s.charAt(i) == '0') {
								f = true;
								break;
							}
							w[i + x] = s.charAt(i) - '0';
						}
						else if (w[i - x] == s.charAt(i) - '0') {
							if (s.charAt(i) == '0')
								w[i + x] = s.charAt(i) - '0'; 
						}
					}
					else if (i + x < s.length() && i - x < 0) {
						w[i + x] = s.charAt(i) - '0';
					}
					else if (i + x >= s.length() && i - x >= 0) {
						if (w[i - x] == -1) w[i - x] = s.charAt(i) - '0';
						else if (w[i - x] != s.charAt(i) - '0') {
							f = true;
							break;
						}
					}
				}
				if (f) print.println(-1);
				else {
					for (int i = 0; i < s.length(); ++i) if (w[i] == -1) w[i] = 0;
					for (int i = 0; i < s.length(); ++i) print.print(w[i]);
					print.println();
				}
			}
		}
	}

	static class Reader {
		BufferedReader reader;
		StringTokenizer tokenizer;

		public Reader(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			tokenizer = null;
		}

		public String next() throws IOException {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(reader.readLine());
			}
			return tokenizer.nextToken();
		}

		public boolean hasNext() throws IOException {
			String str;
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				str = reader.readLine();
				if (str == null)
					return false;
				tokenizer = new StringTokenizer(str);
			}
			return true;
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
	}
}
