#2327 Word Parts

1 s   128 MB  

Description

Given a base word, original, and a compound word, compound, decide if the compound word is valid. A compound word is valid if and only if it is comprised solely of a concatenation of prefixes and/or suffixes of original. That is, if the compound word can be partitioned into N parts, such that each part is equal to either a prefix or a suffix of original, then it is valid.

 

Input

First line, a number of test cases T( T <= 50)

Next line, original word.

Next line, compound word.

 

original will contain between 1 and 50 characters, inclusive.

original will consist only of uppercase letters (A-Z).

compound will contain between 1 and 50 characters, inclusive.

compound will consist only of uppercase letters (A-Z).

 

Output

If the word is invalid, print -1. Otherwise, print the minimum value of N for which this is possible. The entire base word original is considered a valid prefix/suffix of itself.

 

Sample Input

Sample Output

3
ANTIDISESTABLISHMENTARIANISM
ANTIDISIANISMISM
ANTIDISESTABLISHMENTARIANISM
ESTABLISHMENT
ABBBAABABBBAABBABBABABBABAABBAABBBBBABBABABBABAABB
BBBAABABBBAABBABBABABBABAABBAABBBBBABBABABBABAABAA
3
-1
17

Source

Single Round Match 156 Round 1 - Division II, Level Three