$N$ đồng xu được xếp thành một hàng ngang. Mỗi đồng xu có thể đang ở mặt ngửa hoặc mặt sấp.

Bạn có thể thực hiện thao tác sau không giới hạn số lần:

• Chọn hai đồng xu liền kề và đang cùng một mặt, rồi lật cả hai đồng xu đó.

Lật một đồng xu sẽ làm mặt ngửa thành mặt sấp và mặt sấp thành mặt ngửa.

Cho trạng thái ban đầu của các đồng xu, hãy xác định xem có thể làm cho tất cả đồng xu đều ngửa lên được hay không, và nếu có thể, hãy tìm số thao tác tối thiểu cần thực hiện.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ dữ liệu $T$. ($1 \le T \le 10\,000$)

Mỗi bộ dữ liệu gồm hai dòng:

• Dòng đầu chứa số nguyên $N$ – số lượng đồng xu. ($1 \le N \le 1\,000\,000$)
• Dòng thứ hai chứa xâu $S$ độ dài $N$ mô tả trạng thái của các đồng xu. Với mọi $1 \leq i \leq N$, ký tự thứ $i$ của $S$ là H nếu đồng xu thứ $i$ đang ngửa, và là T nếu đồng xu thứ $i$ đang sấp.

Tổng giá trị $N$ trên tất cả các bộ dữ liệu không vượt quá $1\,000\,000$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa số thao tác tối thiểu cần thực hiện để tất cả đồng xu đều ngửa lên. Nếu không thể, in ra $-1$.

Ví dụ

Dữ liệu vào 1

2
5
HTHHT
2
HT

Dữ liệu ra 1

3
-1