環狀字串的最短共同循環節

題目敘述

有兩個姊妹各擁有一個環狀字串(字元只會出現小寫英文字母), 有天他們想知道他們的字串有多友好, 兩個字串的友好程度就是他們的最短共同循環節長度, 而環狀字串的循環節是指經過重複連接可以得到原環狀字串的子字串(例如$\str{abcabc}$裡$\str{bca},~\str{bcabca}$都算是一個循環節)。請你幫忙他們解決這個問題。

輸入說明

第1行有一個$T$表示測試資料筆數，每筆測試資料有兩行分別代表姊姊和妹妹的字串

$1 \leq T \leq 10$
字串長度$ \leq 100000$

輸出說明

對於每筆測試資料輸出一行表示最短共同循環節長度，不存在則輸出$0$

範例輸入

2
abcabc
abc
aaaaaaa
aaaaaa

範例輸出

3
1

提示

環狀字串就是最後一個字元的下一個字元會跳到第一個字元，若存在兩個字串$Sa,~Sb$環狀字串$Sa+Sb,~Sb+Sa$是環狀相等的

Judge Setting

run-time limit: 40 ms
memory limit: 65536000 byte
測資數量: 0