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>
using namespace std;
using namespace std::chrono;
vector<string> alpha{"a", "b", "c", "d", "e", "f", "g", "h", "i",
                     "j", "k", "l", "m", "n", "o", "p", "q", "r",
                     "s", "t", "u", "v", "w", "x", "y", "z"};
vector<string> ALPHA{"A", "B", "C", "D", "E", "F", "G", "H", "I",
                     "J", "K", "L", "M", "N", "O", "P", "Q", "R",
                     "S", "T", "U", "V", "W", "X", "Y", "Z"};
int GCD(int a, int b) {
  if (a == 0) return b;
  if (b == 0) return a;
  return GCD(b, a % b);
}
int LCM(int a, int b) { return (a * b) / GCD(a, b); }
int search(vector<int> a, int b) {
  int m = a.size() / 2;
  vector<int> h;
  int i = -1;
  if (b == a[m]) return m;
  if (a.size() == 1 && b != a[m]) return -1;
  if (b < a[m]) {
    h = {a.begin(), a.begin() + m};
    i = 0;
  } else {
    h = {a.begin() + m, a.end()};
    i = m;
  }
  int s = search(h, b);
  return s < 0 ? -1 : i + s;
}
int searchU(vector<int> a, int b) {
  for (int i = 0; i < a.size(); i++) {
    if (a[i] == b) return i;
  }
  return -1;
}
int MIN(vector<int> a) {
  int best = pow(2, 31) - 1;
  for (auto b : a) {
    if (b < best) best = b;
  }
  return best;
}
int min_i(vector<int> a) {
  int best = pow(2, 31) - 1;
  int index;
  for (int i = 0; i < a.size(); i++) {
    if (a[i] < best) {
      best = a[i];
      index = i;
    }
  }
  return index;
}
float min(vector<float> a) {
  float best = pow(2, 31) - 1;
  for (auto b : a) {
    if (b < best) best = b;
  }
  return best;
}
int MAX(vector<int> a) {
  int best = -1 * (pow(2, 31) - 1);
  for (auto b : a) {
    if (b > best) best = b;
  }
  return best;
}
int max_i(vector<int> a) {
  int best = -1 * (pow(2, 31) - 1);
  int index = -1;
  for (int i = 0; i < a.size(); i++) {
    if (a[i] > best) {
      best = a[i];
      index = i;
    }
  }
  return index;
}
void printVector(vector<int> v) {
  for (auto i : v) {
    cout << i << " ";
  }
  cout << '\n';
}
bool in(int val, vector<int> v) {
  for (auto i : v) {
    if (i == val) {
      return true;
    }
  }
  return false;
}
bool in(string val, vector<string> v) {
  for (auto i : v) {
    if (i == val) {
      return true;
    }
  }
  return false;
}
int sum(vector<int> v) {
  int sum = 0;
  for (auto i : v) {
    sum += i;
  }
  return sum;
}
float sq(int a) { return (float)a * a; }
bool sorted(vector<int> a) {
  for (int i = 1; i < a.size(); i++) {
    if (a[i] < a[i - 1]) {
      return false;
    }
  }
  return true;
}
vector<int> dijkstras(vector<vector<pair<int, int>>> g, int s, int e) {
  vector<int> dist(g.size(), pow(2, 31) - 1);
  dist[s] = 0;
  priority_queue<pair<int, int>, vector<pair<int, int>>,
                 greater<pair<int, int>>>
      next;
  next.push({0, s});
  vector<bool> visited(g.size(), false);
  vector<int> prev(g.size(), -1);
  while (!next.empty()) {
    visited[next.top().second] = true;
    for (auto i : g[next.top().second]) {
      if (!visited[i.first]) {
        if (dist[next.top().second] + i.second < dist[i.first]) {
          dist[i.first] = dist[next.top().second] + i.second;
          prev[i.first] = next.top().second;
        }
        next.push({dist[i.first], i.first});
      }
    }
    next.pop();
  }
  vector<int> path = {e};
  while (true) {
    if (prev[path.back()] == -1) break;
    path.push_back(prev[path.back()]);
  }
  reverse(path.begin(), path.end());
  return path;
}
int main() {
  int cases = 1;
  cin >> cases;
  for (int _case = 0; _case < cases; _case++) {
    string s;
    cin >> s;
    int w;
    cin >> w;
    vector<int> a(s.size(), 1);
    for (int i = 0; i < s.size(); i++) {
      if (s[i] == '0') {
        if (i - w >= 0) a[i - w] = 0;
        if (i + w < s.size()) a[i + w] = 0;
      }
    }
    bool d = true;
    for (int i = 0; i < a.size(); i++) {
      if (s[i] == '1') {
        int y = 0;
        if (i - w >= 0) {
          if (a[i - w] == 1) y++;
        }
        if (i + w < a.size()) {
          if (a[i + w] == 1) y++;
        }
        if (y == 0) {
          d = false;
          break;
        }
      }
    }
    if (!d) {
      cout << -1 << '\n';
      continue;
    }
    for (auto i : a) {
      cout << i;
    }
    cout << '\n';
  }
}
