「BONAN」
「MATENON」

為了能夠與更多外星人溝通，海果決定要更努力的學習宇宙語！

每個宇宙語的句子都是由數個宇宙語符號組合成的。而海果發現只要句子中出現連續相同的符號，或句子開頭的符號與結尾的符號相同，她就需要花更多的力氣背。對此，她定義一個句子是難記的若它滿足以下兩條件：

• 該句子的符號數量至少為 $2$
• 該句子的開頭符號與結尾符號相同，或存在兩相鄰且相同的符號

舉例來說，下圖顯示了三個宇宙語句子，前兩個都是難記的，而最後一個不是：

PEGGJOV=MOVLOV,PIVOU,BOVVU=VUV
ANTAŬDIRITA
KAMARADO

了解到哪些句子是難記的後，海果想要將一個大句子拆解成許多段小句子，使得每一個小句子都不是難記的，同時盡可能最小化小句子的數量來幫助她快速記憶（注意是數量不是種類）。

更明確的說，假設一句子有 $n$ 個符號 $s_1{s}_2\dots s_n$，請找到最小的 $k$ 使得存在 $l_1,r_1,l_2,r_2,\dots ,l_k,r_k$ 滿足：

• $\mathrm{\forall }1\le i\le k,l_i\le r_i$
• $\mathrm{\forall }1\le i<k,r_i+1=l_{i+1}$
• $l_1=1,r_k=n$
• $\mathrm{\forall }1\le i\le k,s_{l_i}{s}_{l_i+1}\dots s_{r_i}$ 這個句子是不難記的

但海果不太擅長做這件事，現在給定她想要背的 $N$ 個句子，對於每一個句子，你能幫助她計算至少需要拆解成幾個小句子嗎？