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;
long long int ll_max(long long int a, long long int b, long long int c) {
  return max(a, max(b, c));
}
int int_max(int a, int b, int c) { return max(a, max(b, c)); }
long long int ll_min(long long int a, long long int b, long long int c) {
  return min(a, min(b, c));
}
int int_min(int a, int b, int c) { return min(a, min(b, c)); }
long long int max(int a, long long int b) { return max((long long int)a, b); }
long long int min(int a, long long int b) { return min((long long int)a, b); }
long long int min(long long int a, int b) { return min(a, (long long int)b); }
long long int max(long long int a, int b) { return max(a, (long long int)b); }
long long int maximum(long long int a[], long long int n) {
  long long int max1 = LLONG_MIN;
  for (long long int i = 0; i < n; i++) {
    max1 = max(max1, a[i]);
  }
  return max1;
}
long long int minimum(long long int a[], long long int n) {
  long long int min1 = LLONG_MAX;
  for (long long int i = 0; i < n; i++) {
    min1 = min(min1, a[i]);
  }
  return min1;
}
long long int dx[] = {0, 0, 1, -1};
long long int dy[] = {1, -1, 0, 0};
long long int power(long long int x, long long int y, long long int m) {
  if (y == 0) return 1;
  long long int a = power(x, y / 2, m);
  if (y % 2) {
    return (a * ((a * x) % m)) % m;
  } else {
    return (a * a) % m;
  }
}
long long int mod_inverse(long long int x, long long int m) {
  return power(x, m - 2, m);
}
long long int fact(long long int n, long long int m) {
  if (n <= 1) return 1;
  return (fact(n - 1, m) * n) % m;
}
long long int ncr(long long int n, long long int r, long long int m) {
  if (r > n) return 0;
  long long int n1 = 1, d1 = 1, d2 = 1;
  n1 = fact(n, m);
  d1 = fact(r, m);
  d2 = fact(n - r, m);
  long long int ans = mod_inverse((d1 * d2) % m, m);
  ans = (ans * n1) % m;
  return ans;
}
int gcd(int a, int b) {
  if (a == 0 || b == 0) return max(a, b);
  if (a < b) return gcd(b, a);
  if (a % b == 0) return b;
  return gcd(b, a % b);
}
int ispal(string s) {
  int len = s.size();
  int flag = 1;
  for (int i = 0; i < len; ++i) {
    if (s[i] != s[len - i - 1]) {
      flag = 0;
      break;
    }
  }
  return flag;
}
long long int sroot(long long int n, long long int low = 1,
                    long long int high = 1e9 + 1) {
  if (low == high) return low;
  if (low == high - 1) {
    if (high * high <= n)
      return high;
    else
      return low;
  }
  long long int mid = (low + high) / 2;
  long long int a = mid * mid;
  if (a > n)
    return sroot(n, low, mid - 1);
  else
    return sroot(n, mid, high);
}
long long int croot(long long int n, long long int low = 1,
                    long long int high = 1e6 + 1) {
  if (low == high) return low;
  if (low == high - 1) {
    if (high * high * high <= n)
      return high;
    else
      return low;
  }
  long long int mid = (low + high) / 2;
  long long int a = mid * mid * mid;
  if (a > n)
    return croot(n, low, mid - 1);
  else
    return croot(n, mid, high);
}
bool sortbysec(const pair<long long int, long long int> &a,
               const pair<long long int, long long int> &b) {
  return (a.second < b.second);
}
class solver {
 public:
  void solve() {
    string s;
    cin >> s;
    long long int x;
    cin >> x;
    long long int n = s.length();
    long long int dp1[n + 5], dp2[n + 5];
    string w = "";
    for (long long int i = 0; i < n; i++) w += "1";
    long long int f = 0;
    for (long long int i = 0; i < n; i++) {
      if (s[i] == '0') {
        long long int g = 0;
        if (i - x >= 0) {
          w[i - x] = '0';
        }
        if (i + x < n) {
          w[i + x] = '0';
        }
      }
    }
    if (f == 0) {
      for (long long int i = 0; i < n; i++) {
        long long int g = 0;
        if (s[i] == '1') {
          if (i - x >= 0) {
            if (w[i - x] == '1') g = 1;
          }
          if (i + x < n) {
            if (w[i + x] == '1') g = 1;
          }
          if (g == 0) f = -1;
        }
      }
    }
    if (f == -1)
      cout << "-1\n";
    else
      cout << w << "\n";
  }
};
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(NULL);
  std::cout.tie(NULL);
  int test = 1, c = 1;
  cin >> test;
  while (test--) {
    solver o;
    o.solve();
  }
}
