Given two binary strings, A (of length 10) and B (of length 5), 

output 1 if B is a substring of A and 0 otherwise.



Input

The first line contains the number of test cases n. This is followed by n lines each consisting of pairs of binary strings A and B separated by a single space.



Output

output 1 if B is a substring of A and 0 otherwise.



Example

Input:
1
1010110010 10110

Output:
1
def main():
    test = int(raw_input())
    i = 0
    while i < test:
        l = raw_input().split()
        a = l[0]
        b = l[1]
        if b in a:
            print(1)
        else:
            print(0)
        i += 1


if __name__ == '__main__':
    main()