计算机极客喜欢树，蚂蚁也喜欢树。因此，我们给定一棵树，上面有两只蚂蚁在爬行——左蚂蚁（Left Ant）和右蚂蚁（Right Ant），爬行方式如图所示（蚂蚁沿着虚线路径爬行）。它们从树干的底端出发，位于树干的两侧。如果左蚂蚁从根部向上爬，经过一条边需要 2 秒；如果向根部向下爬，则需要 1 秒。右蚂蚁的速度是左蚂蚁的两倍。当两只蚂蚁相遇时，它们都会掉头并向相反方向爬行。如果任何一只蚂蚁从树上爬到了地面，它会立即开始从树干的另一侧向上爬。此外，蚂蚁非常微小，即使在显微镜下也几乎不可见（图中为了方便观察特意画大了）。你的任务是编写一个程序，计算蚂蚁第二次掉头的时刻。

输入格式

输入的第一行包含一个整数 $t$ ($1 \leqslant t \leqslant 1000$)，表示输入中描述的测试用例数量。

每个测试用例的描述包含两行。第一行包含一个偶数 $n$ ($2 \leqslant n \leqslant 100\,000\,000$)，表示树的边数。第二行包含树的描述。这是一个由 $\frac{n}{2}$ 个字符组成的字符串，表示一个 $2n$ 位的二进制数，以十六进制形式书写（使用数字和字母 a 到 f）。该数字展示了假设右蚂蚁静止不动时，左蚂蚁绕树一周的路径。该数字的连续位（从左开始）表示左蚂蚁是沿着对应的边远离树根（位 1）还是向着树根（位 0）爬行。树根处有一段树干，即从树根出发恰好有一条边。

输入文件的大小不超过 50 MB，这远大于程序可用的内存限制。

输出格式

你的程序应输出 $t$ 行，包含对应测试用例的答案。每个答案应表示蚂蚁第二次掉头的时刻（以秒为单位），以不可约分数 $p/q$ 的形式给出（/ 周围没有空格），其中 $p$ 和 $q$ 为正整数。如果答案是整数，则显然 $q=1$。

样例

输入 1

1
28
fb1da30d1b7230

输出 1

282/5

说明 1

样例数据对应于上图，并转换为以下位序列： 1111 1011 0001 1101 1010 0011 0000 1101 0001 1011 0111 0010 0011 0000