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
def main():
    ntests = int(input())
    S=[]
    W=[]
    x=[]
    for i in range(ntests):
        S.append(list(input()))
        x.append(int(input()))
        W.append([ "X" for x in range(len(S[i])) ])

    for i in range(ntests):
        m = []
        for letter in range(len(S[i])):
            left = bounds(letter-x[i], len(W[i]))   # check if w[i-x] exists
            right = bounds(letter+x[i], len(W[i]))  # check if w[i+x] exists
            if left and not right:
                if not adjust(W[i], S[i][letter], letter - x[i]):
                    break
            if right and not left:
                if not adjust(W[i],S[i][letter],letter+x[i]):
                    break
            # if both exist and si is 0 then both are 0 if si is 1 then on eof them has to be one
            if right and left:
                if S[i][letter] == "0":
                    if not adjust(W[i],S[i][letter],letter+x[i]) or not adjust(W[i], S[i][letter], letter - x[i]):
                        break
                else:
                    # append the positions of the chars to m
                    m.append((letter+x[i],letter-x[i]))
            if (not left) and (not right) and (S[i][letter] == "1"):
                W[i] = "-1"
                break
        # check m if both of any of the position pairs is zero then S is corrupt
        for pair in m:
            # if the word is already invalid skip
            if W[i] == list("-1"):
                break
            if conflict(W[i], pair[0], pair[1]):
                W[i] = list("-1")
                break

    for word in range(len(W)):
        for letter in range(len(W[word])):
            if W[word][letter] == "X":
                W[word][letter] = "1"
    for word in W:
        print("".join(word))


# return true if successfully adjusted and false if conflicting adjustment
def adjust(W, adjustment, position):
    if W[position] !='X':
        if W[position] != adjustment:
            W[:] = "-1"
            return False
    W[position] = adjustment
    return True

# one of pos1 and pos2 must be 1, if not then invalid word
def conflict(word,pos1,pos2):
    if word[pos1] == "0" and word[pos2] == "0":
        return True
    else:
        return False


def bounds(testcase, upperlimit, lowerlimit = 0):
    if testcase>=lowerlimit and testcase<upperlimit:
        return True
    else:
        return False

if __name__ == '__main__':
    main()