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

SAMPLE INPUT
1
aaa
a

SAMPLE OUTPUT
1

Explanation

In sample the common divisors string is only "a".

见题面

见题面