该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

在音乐制作中，节奏是构成音乐的基本元素之一。音乐家们使用不同的音符来创作旋律，其中正拍（'+'）和反拍（'-'）是构成节奏的基础。在一首乐曲中，音符序列的记录可以表示为一个由正负号组成的字符串 $S$ 。

题目描述

音乐制作人 小 $y$ 正在构想一首乐曲的乐段数量。他有一串由正拍（'+'）和反拍（'-'）组成的音符序列 S，长度为 n。为了使乐曲更加和谐，要求每个乐段的开头音符与末尾音符 不相同 。

问 小 $y$ 最少可以将这首乐曲分成多少个乐段？

如果无法划分，输出 "-1" 即可。

例如 ：

1. +++--- ，可以分成一个乐段。
2. ++--++，可以分成两个乐段。
3. ++-++，无法划分。
4. +--++--+，最少分成两个乐段，+-和-++--+即可

输入格式

第一行一个整数 T ，表示测试用例数量。

对于每组数据： 第一行包含一个整数 n ，表示乐曲的音符数量。 第二行一个长度为 n 的字符串 S ，表示音符序列。

输出格式

输出 T 行，每行一个整数，表示划分的最少乐段数量。

5
6
+++---
6
++--++
5
++-++
8
+--++--+
10
++--++++++

1
2
-1
2
2

提示

嘿嘿，大家可以试着自己来构造不同数量的乐段。是否存在最少分成三个或者四个乐段的情况呢~~

【数据范围】