A96997.【ZZSR #1】完美洗牌

wmg 邀请你参加一场三个人有四个桂的斗地主。

---

坐在你上家的 cjdst 上来就是一个完美洗牌，已知这副牌有 $n$ 张，点数分别为23456789TJQKA。这些牌没有花色，即你可以认为任意两张点数相同的牌为同样的牌。同时这副牌里可能有超过四张点数相同的牌。

我们定义一次完美洗牌为：

• 先将这 $n$ 张牌 从牌堆顶至牌堆底分别由 $1\sim n$ 编号
• 编号为 $i(1\le i\le \frac{n}{2})$ 的牌移动到从牌堆顶到牌堆底的第 $2i-1$ 个位置。
• 编号为 $i(\frac{n}{2}<i\le n)$ 的牌移动到从牌堆顶到牌堆底的第 $2i-n$ 个位置。

以一个牌堆从顶至底顺序为234567 举例来说，一次完美洗牌后，从牌堆顶至底的顺序变为253647。

聪明的你一定发现，不管牌张数以及点数如何，必定存在一个正整数 $k$，使得 $k$ 次完美洗牌后牌堆与初始时的牌堆相同，所以你想开挂计算出最小的 $k$。可以证明最小的 $k$ 一定小于 $n$。

本题数据使用多组输入输出，第一行输入一个正整数 $T$ 表示数据组数。

对于每组数据输入共两行，第一行输入一个正整数 $n$，含义如题。

接下来一行输入 $n$ 个字符表示初始时牌堆从顶至底的点数，保证只会出现23456789TJQKA。

对于每组数据输出共一行一个正整数，表示最小的 $k$。

特殊说明：

保证 $n$ 是偶数。

样例解释：

对于样例一中的第三组测试数据：

初始时：223222333232
第一次：232333222322
第二次：223222333232

数据范围：

对于 $100\%$ 的测试数据，$1\le T \le 10,1\le n\le 10^3$。