Play with Strings

4.3

3 votes
Problem

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

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

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

Editor Image

?