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>
#pragma GCC optimize("O3")
using namespace std;
const long long int MAXN = 1e5 + 5;
const long long int mod = 1e9 + 7;
long long int it = 0, ans = 0;
template <typename temp>
void sp(temp x) {
  cout << x << " ";
}
template <typename temp>
void np(temp x) {
  cout << x << "\n";
}
template <typename Arg1, typename... Args>
void sp(Arg1 arg1, Args... args) {
  cout << arg1 << " ";
  sp(args...);
}
template <typename Arg1, typename... Args>
void np(Arg1 arg1, Args... args) {
  cout << arg1 << "\n";
  np(args...);
}
template <typename temp>
void spv(temp T, long long int n) {
  for (int i = 0; i < n; i++) sp(T[i]);
}
template <typename temp>
void npv(temp T, long long int n) {
  for (int i = 0; i < n; i++) np(T[i]);
}
template <typename T>
T modpow(T base, T exp, T modulus) {
  base %= modulus;
  T result = 1;
  while (exp > 0) {
    if (exp & 1) result = (result * base) % modulus;
    base = (base * base) % modulus;
    exp >>= 1;
  }
  return result;
}
template <typename T>
T modinv(T base, T exp) {
  return modpow(base, exp - 2, exp);
}
long long int spf[MAXN];
void sieve() {
  spf[1] = 1;
  for (auto i = 2; i < MAXN; i++) spf[i] = i;
  for (auto i = 4; i < MAXN; i += 2) spf[i] = 2;
  for (auto i = 3; i * i < MAXN; i++) {
    if (spf[i] == i) {
      for (auto j = i * i; j < MAXN; j += i)
        if (spf[j] == j) spf[j] = i;
    }
  }
  return;
}
vector<long long int> getFactorization(long long int x) {
  vector<long long int> res;
  while (x != 1) {
    res.push_back(spf[x]);
    x = x / spf[x];
  }
  return res;
}
void check() {
  string s;
  long long int k;
  cin >> s >> k;
  long long int n = s.size();
  string w(n, '1');
  for (int i = 0; i < n; i++) {
    if (s[i] == '0') {
      if (i + k < n) w[i + k] = '0';
      if (i - k >= 0) w[i - k] = '0';
    }
  }
  for (int i = 0; i < n; i++) {
    bool ok = false;
    ok = ok || (i + k < n && w[i + k] == '1');
    ok = ok || (i - k >= 0 && w[i - k] == '1');
    if (s[i] != ok + '0') {
      np(-1);
      return;
    }
  }
  np(w);
  return;
}
int32_t main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  ;
  long long int t = 1;
  cin >> t;
  while (t--) check();
  return 0;
}
