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
#include <bits/stdc++.h>
const int alldx[] = {1, -1, 0, 0, 1, -1, 1, -1};
const int alldy[] = {0, 0, 1, -1, 1, -1, -1, 1};
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
struct matrix {
  int a[2][2];
  matrix operator*(matrix &b) {
    matrix product;
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        product.a[i][j] = 0;
      }
    }
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++)
        for (int k = 0; k < 2; k++) product.a[i][k] += (a[i][j] * b.a[j][k]);
    return product;
  }
  matrix operator+(matrix &b) {
    matrix sum;
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++) sum.a[i][j] = 0;
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++) sum.a[i][j] += a[i][j] + b.a[i][j];
    return sum;
  }
  matrix operator-(matrix &b) {
    matrix difference;
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++) difference.a[i][j] = 0;
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++) difference.a[i][j] += a[i][j] - b.a[i][j];
    return difference;
  }
};
using namespace std;
void task() {
  string s;
  cin >> s;
  int k;
  cin >> k;
  int n = s.size();
  string ans = "";
  for (int i = 0; i < n; i++) {
    ans += '1';
  }
  for (int i = 0; i < n; i++) {
    if (s[i] == '0') {
      if (i + k < n) {
        ans[i + k] = '0';
      }
      if (i - k >= 0) {
        ans[i - k] = '0';
      }
    }
  }
  bool pos = true;
  for (int i = 0; i < n; i++) {
    if (s[i] == '1') {
      if (((i + k < n) && ans[i + k] == '1') ||
          (i - k >= 0 && ans[i - k] == '1')) {
        pos = true;
      } else {
        pos = false;
        break;
      }
    }
  }
  if (!pos) {
    cout << "-1\n";
  } else {
    cout << ans << endl;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int TT;
  cin >> TT;
  while (TT--) {
    task();
  }
  return 0;
}
