No testdata at current.

题目描述

我们学校校园里有许多的小猫，小狗(o(^▽^)o)，小猫，小狗都是非常可爱的动物，想必大家都很喜欢。

现在小劉同学拿来数只猫和狗，将它们放在一个并列排列的连续的房间内，每个房间都有一个窗户能够看到第二个房间里边，一共n个房间。

我们假设猫能够很确定的分清楚对方是猫还是狗，狗不能十分确定的分清楚对方是猫还是狗。 更准确的说，猫的判断总是正确的，而狗的判断不一定正确。

给你一个长度为n-1的01字符串，字符串中只含有0和1，1表示第i个房间的动物判断第i+1个房间的动物是狗，而0表示表示第i个房间的动物判断第i+1个房间的动物不是狗。

由于小劉同学忘记了拿来的狗和猫的数量，请你帮助小劉同学判断在狗的数量最少的情况下，有几只狗，几只猫。

输入描述

第一行一个正整数 T ( 1 <= T <= 10³ ) 表示数据组数。

每组测试数据描述如下：

第一行一个正整数 n ( 2 <= n <= 10³ ), n 表示猫和狗总的数量。

第二行一个字符串 s , 字符串的长度为那 n-1

保证所有组数据中的 n 之和不超过 10⁵ 。

输出描述

在狗的数量最少的情况下，求出每一组数据中猫和狗的数量，先输出猫再输出狗，用空格隔开。

样例

3
5
0001
5
1010
7
101110

1 4
2 3
3 4

解释

对题目中样例的解释：

第一个样例：猫，猫，猫，猫，狗

第二个样例：猫，狗，猫，狗，猫

第三个样例：猫，狗，猫，狗，猫，狗，猫

限制范围

每个测试样例限制为1s, 248Mb。