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
from sys import stdin,stdout
from collections import defaultdict
import math
input=stdin.readline
def print(x):stdout.write(str(x)+'\n')
for _ in range(int(input())):
    s=input().strip()
    x=int(input())
    n=len(s)
    l=[[] for i in range(n)]
    ans=''
    f=0
    d=defaultdict(list)
    for i in range(n):
        if i>=x:
            l[i-x].append(i)
            d[i].append(i-x)
        if i+x<n:
            l[i+x].append(i)
            d[i].append(i+x)
        if i<x and i+x>=n and s[i]!='0':
            f=1
    #print(l)
    if f==1:
        print(-1)
        continue
    
    f=0
    for i in range(n):
        if len(d[i])>1 and s[i]=='1':
            if len(l[i-x])==1:
                l[i+x].remove(i)
                d[i].remove(i+x)
            elif len(l[i+x])==1:
                l[i-x].remove(i)
                d[i].remove(i-x)
            elif len(l[i+x])==2 and s[l[i+x][0]]==s[l[i+x][1]]:
                l[i-x].remove(i)
                d[i].remove(i-x)
            elif len(l[i-x])==2 and s[l[i-x][0]]==s[l[i-x][1]]:
                l[i+x].remove(i)
                d[i].remove(i+x)
    for i in range(n):
        if len(d[i])>1 and s[i]!='0':
            if len(l[i-x])==1 :
                l[i+x].remove(i)
                d[i].remove(i+x)
            elif len(l[i+x])==1:
                l[i-x].remove(i)
                d[i].remove(i-x)
            elif len(l[i+x])==2 and s[l[i+x][0]]==s[l[i+x][1]]:
                l[i-x].remove(i)
                d[i].remove(i-x)
            elif len(l[i-x])==2 and s[l[i-x][0]]==s[l[i-x][1]]:
                l[i+x].remove(i)
                d[i].remove(i+x)
    #print(l)
    for i in l:
        if len(i)>1 and s[i[0]]!=s[i[1]]:
            f=1
            break
    if f==1:
        print(-1)
    else:
        for i in l:
            if len(i)>0:
                ans+=s[i[0]]
            else:
                ans+='1'
        print(ans)
            