有 $N$ 枚硬幣排成一列。每枚硬幣顯示正面或反面。
你可以重複以下操作任意次：
- 選擇兩枚相鄰且顯示相同面的硬幣，並將它們都翻面。
翻轉顯示正面的硬幣會變成反面，翻轉顯示反面的硬幣會變成正面。
給定每枚硬幣的狀態，判斷是否能讓所有硬幣顯示正面，如果可以，求所需的最小操作次數。
輸入格式
第一行給定測試資料的組數 $T$。($1 \le T \le 10\,000$)
每組測試資料的第一行給定硬幣的數量 $N$。($1 \le N \le 1\,000\,000$)
每組測試資料的第二行給定一個長度為 $N$ 的字串 $S$，表示每枚硬幣的狀態。對於所有 $1 \leq i \leq N$，$S$ 的第 $i$ 個字元是 H（若第 $i$ 枚硬幣為正面）或 T（若為反面）。
所有測試資料的 $N$ 總和不超過 $1\,000\,000$。
輸出格式
對於每組測試資料，輸出在所有硬幣顯示正面的條件下所需的最小操作次數。若不可能，則輸出 $-1$。
範例
輸入 1
2 5 HTHHT 2 HT
輸出 1
3 -1