Tade có một xâu \(s\) bao gồm các chữ cái Latinh viết thường. Anh ấy quyết định xóa hai ký tự liên tiếp khỏi xâu \(s\) và thắc mắc có bao nhiêu xâu khác nhau có thể nhận được sau thao tác đó.

Ví dụ, Tade có xâu aaabcc. Tade có thể nhận được các xâu khác nhau sau: abcc (bằng cách xóa hai ký tự đầu tiên hoặc ký tự thứ hai và thứ ba), aacc (bằng cách xóa ký tự thứ ba và thứ tư), aaac (bằng cách xóa ký tự thứ tư và thứ năm) và aaab (bằng cách xóa hai ký tự cuối cùng).

Input

• Dòng đầu tiên chứa một số nguyên \(t\) (\(1 \le t \le 10^4\)) — số lượng bộ test.
• Các dòng tiếp theo mô tả các bộ test:
  • Dòng đầu tiên của mỗi bộ test chứa một số nguyên \(n\) (\(3 \le n \le 2 \cdot 10^5\)).
  • Dòng thứ hai của mỗi bộ test chứa một xâu \(s\) có độ dài \(n\) bao gồm các chữ cái Latinh viết thường.
• Đảm bảo rằng tổng của \(n\) trên tất cả các bộ test không vượt quá \(2 \cdot 10^5\).

Output

• Với mỗi bộ test, in ra một số nguyên duy nhất — số lượng xâu phân biệt có thể nhận được bằng cách xóa hai chữ cái liên tiếp.

Scoring

• Subtask \(1\) \((10\%)\): \(n \le 10\).
• Subtask \(2\) \((10\%)\): Hai ký tự liên tiếp luôn bằng nhau.
• Subtask \(3\) \((30\%)\): Các ký tự ở vị trí lẻ luôn bằng nhau.
• Subtask \(4\) \((50\%)\): Không có ràng buộc gì thêm.

Example

7
6
aaabcc
10
aaaaaaaaaa
6
abcdef
7
abacaba
6
cccfff
4
abba
5
ababa

4
1
5
3
3
3
1