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

见题面

见题面