Lacy 背單字

題目敘述

聰明的 Lacy 喜歡背單字。但 Lacy 患有一種罕見的學習障礙，如果兩個單字經過若干次旋轉操作後會一樣 Lacy 會把他們當成同一個單字。

一個單字 $S=s_1 s_2 s_3 ... s_n$ 經過一次旋轉操作後會變成 $S=s_2 s_3 ... s_n s_1$

一天　Lacy 得到了一個單字表, 上面都是 Lacy 沒背過的單字, Lacy 想要計算背完這個單字表後他會多學會幾個新的單字(對 Lacy 而言), 但他忙著準備大會考, 所以想請你替他算算單字表上有幾個不同的單字。

輸入的第一行包含一個整數 $T(T\leq 20)$，代表接下來有 $T$ 個單字表。每個測試有 $n+1$ 行, 第$1$行是 $n$, 接著 $n$ 行每行是一單字 $W_i$。

$n \leq 1000$

$W_i$ 只由小寫英文字母組成

$\sum{|W_i|} \leq 100000$

對於每個單字表輸出一行, 表示對 Lacy 而言這個單字表有幾個不同的單字。

2
2
abc
bca
2
aa
aaa

1
2

$ n \leq 2 $

$ n \leq 10 $

無額外限制

run-time limit: 1000 ms
memory limit: 1048576 byte
測資數量: 3