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 f, a, b, x, c, q, d, w, a1, b1, c1, a2, g, b2, c2, n, m, i, j, k, l,
    o, p, t, y, r, q1, q2, mx, mx2, mn = 1000000000000, mn2 = 1000000000000;
string s, s1, s2, s3;
bool used[100005];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> t;
  for (y = 0; y < t; y++) {
    cin >> s >> x;
    q = 0;
    s2 = "";
    for (i = 0; i < s.size(); i++) {
      used[i] = 0;
      s2 = s2 + '0';
    }
    for (i = 0; i < s.size(); i++) {
      if (s[i] == '0') {
        if (i - x >= 0) {
          if (s2[i - x] == '1') q = 1;
          s2[i - x] = '0';
        }
        if (i + x < s.size()) {
          s2[i + x] = '0';
          used[i + x] = 1;
        }
      }
      if (s[i] == '1') {
        if (i - x >= 0) {
          if (used[i - x] == 1)
            ;
          else {
            s2[i - x] = '1';
            continue;
          }
        }
        if (i + x < s.size()) {
          s2[i + x] = '1';
          continue;
        }
        q = 1;
      }
    }
    if (q == 1)
      cout << -1;
    else
      cout << s2;
    cout << "\n";
  }
}
