Given a string *s* of length *n*, a subsequence of it, is defined as another string *s' = s*_{u}_{1}*s*_{u}_{2}*...s*_{um} where 1 ≤ *u*_{1} < *u*_{2} < ... < *u*_{m} ≤ *n* and *s*_{i} is the *i*th character of *s*. Your task is to write a program that, given two strings *s1* and *s2*, checks whether either *s2* or its reverse is a subsequence of *s1* or not.

The first line of input contains an integer *T*, which is the number of test cases. Each of the next *T* lines contains two non-empty strings *s1* and *s2* (with length at most 100) consisted of only alpha-numeric characters and separated from each other by a single space.

提交代码