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 sys
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__

def getInts():
    return [int(s) for s in input().split()]

def getInt():
    return int(input())

def getStrs():
    return [s for s in input().split()]

def getStr():
    return input()

def listStr():
    return list(input())

import collections as col

def solve():
    S = [int(s) for s in input()]
    X = getInt()
    N = len(S)
    ans = [-1]*N
    pairs = []
    for j in range(N):
        #for each value S[j], we are interested in ans[j-X] and ans[j+X]
        #if both exist and S[j] == 0, they must both also be 0
        #if both exist and S[j] == 1, at least one of them must be a 1, so pairs.append((j-x,j+x))
        #if only one exists and S[j] == 0, that must also be 0
        #if only one exists and S[j] == 1, that must be 1
        #if neither exist, then S[j] must be 0, if not contradiction
        if S[j] == 0:
            if j-X >= 0:
                if ans[j-X] == 1:
                    return -1
                ans[j-X] = 0
            if j+X < N:
                if ans[j+X] == 1:
                    return -1
                ans[j+X] = 0
        elif S[j] == 1:
            if j-X >= 0 and j+X < N:
                pairs.append((j-X,j+X))
            elif j-X >= 0:
                if ans[j-X] == 0:
                    return -1
                ans[j-X] = 1
            elif j+X < N:
                if ans[j+X] == 0:
                    return -1
                ans[j+X] = 1
            else:
                return -1
    for a, b in pairs:
        if ans[a] == 0 and ans[b] == 0:
            return -1
        elif ans[a] == 0:
            ans[b] = 1
        elif ans[b] == 0:
            ans[a] = 1
        else:
            ans[a] = 1
            ans[b] = 1
    for i in range(N):
        if ans[i] == -1:
            ans[i] = 1
    return ''.join(map(str,ans))
        
        
    ans = map(str,ans)
    return ''.join(ans)
    
T = getInt()
for t in range(T):
    print(solve())
