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
import os
import heapq
import sys,threading
import math
import operator
from collections import defaultdict
from io import BytesIO, IOBase

sys.setrecursionlimit(10 ** 5)
threading.stack_size(2**27)


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""


def inpt():
    return [int(k) for k in input().split()]


def main():
    for _ in range(int(input())):
        # p,f=map(int,input().split())
        # s,a=map(int,input().split())
        # w1,w2=map(int,input().split())
        # if(w1>w2):
        #     w1,w2=w2,w1
        #     s,a=a,s
        #
        # sm=p+f
        # c1,c2=0,0
        # sIn=sm//w1
        # if(sIn>s):
        #     sIn=s
        #     s=0
        # else:
        #     s=s-sIn
        # sm-=(sIn*w1)
        # total=(sIn*w1)
        # aIn=sm//w2
        #
        # if (aIn > a):
        #     aIn = a
        #     a = 0
        # else:
        #     a = a - aIn
        # sm-=(aIn*w2)
        # total+=(aIn*w2)
        #
        # if(f>p):
        #     p,f=f,p
        # print(aIn+sIn)
        # temp1,temp2=0,0
        # sIn2,aIn2=0,0
        # while(total>p):
        #     if(aIn>0 and f>=w2):
        #         aIn2+=1
        #         aIn-=1
        #         f-=w2
        #         total-=w2
        #     elif(sIn>0 and f>=w1):
        #         sIn2+=1
        #         sIn-=1
        #         f-=w1
        #         total-=w1
        # if(total<=p):
        #     print((sIn+sIn2+aIn+aIn2))
        #     continue
        # temp1=abs

        s=input()
        x=int(input())
        ans=['1']*(len(s))

        for i in range(len(s)):
            if(s[i]=='0'):
                if (i - x >= 0):
                    ans[i - x] = '0'
                if (i + x < len(s)):
                    ans[i + x] = '0'

        temp=''
        for i in range(len(s)):
            if(i-x>=0 and ans[i-x]=='1'):
                temp+='1'
            elif(i+x<len(s) and ans[i+x]=='1'):
                temp+='1'
            else:
                temp+='0'
        if(s!=temp):
            print(-1)
        else:
            print(''.join(ans))














BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()
    #threading.Thread(target=main).start()
