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.
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).
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.
3 ANTIDISESTABLISHMENTARIANISM ANTIDISIANISMISM ANTIDISESTABLISHMENTARIANISM ESTABLISHMENT ABBBAABABBBAABBABBABABBABAABBAABBBBBABBABABBABAABB BBBAABABBBAABBABBABABBABAABBAABBBBBABBABABBABAABAA
3 -1 17