Shivani loves maths and strings very much. So she used to combine both of them and form new problems. She has recently formulated a new problem described as follows:
String str1 is the divisor of string str2 if and only if there exists a positive integer x such that if we write out string str1 consecutively x times, we get string str2. For example, string "abab" has two divisors — "ab" and "abab".
Input
First line contains an integer , t - denoting the number of testcase.
Each testcase contains two lines.
The first line contains a non-empty string str1.
The second line contains a non-empty string str2.
The strings only consist of lowercase Latin letters.
Output:
Print the number of common divisors of strings str1 and str2.
Constraints:
1 <= t <= 25
1 <= |a|,|b| <= 10^5
In sample the common divisors string is only "a".