Katty ha aprendido recientemente en la escuela como encontrar los divisores de un número. Ella esta muy emocionada con su aprendizaje que decidió determinar los divisores pero de una cadena de texto. Dada la intención de destruir las cadenas de texto a Katty se le ocurrió lo siguiente.

Una cadena de texto "A" es el divisor de una cadena de texto "B" si y sólo si existe un entero positivo X tal que si escribimos la cadena "A" tantas veces como el valor de X, obtenemos como resultado la cadena "B". Por ejemplo, tenemos la cadena "abab":

Ahora Katty quiere escribir un programa que calcule el número de divisores comunes que hay en "dos cadenas de texto". Ayuda a Katty a resolver este problema.

Input

La primera línea del INPUT comienza con un número M que indica el número de casos del problema propuesto. (1 ≤ M ≤ 100)

Cada caso está compuesto de la(s) siguiente(s) linea(s):

- La primera línea de cada caso contiene una cadena A no vacío.
- La segunda línea de cada caso contiene una cadena B no vacío.
- Las longitudes de las cadenas A y B son positivos y no exceden 1000000. Las cadenas sólo contienen letras latinas en minúsculas.

Output

Imprimir un número, el número de divisores comunes entre las cadenas A y B.

Entrada de ejemplo

Nota

En el primer caso los divisores comunes son cadenas "abcd" y "abcdabcd".

En el segundo caso el divisor común es una única cadena "a". La cadena "aa" no se incluye en la respuesta, ya que no es un divisor de cadena "aaa".