小 Misha 坐在老虎机前，想要赢得大奖。这台机器有 $k$ 个槽位，组成一个长度为 $k$ 的字符串。每个槽位可以显示任意十进制数字或问号。初始时，每个槽位都显示问号。

机器内部还保存着一个由 $k$ 个十进制数字组成的秘密字符串。并非所有长度为 $k$ 的十进制字符串都能被机器存储：Misha 找到了这台老虎机的说明书，在第 007 章中列出了所有可能的秘密字符串。为了赢得大奖，玩家需要使 $k$ 个槽位显示的字符串与秘密字符串完全匹配，然后按下大红按钮。然而，当按下按钮时，如果显示的字符串与秘密字符串不同，机器会将秘密字符串和 $k$ 个槽位形成的字符串都转换为整数（可能包含前导零），并告诉玩家其中哪一个更大。注意，如果按下大红按钮时至少有一个槽位显示的是问号，机器则不会给出任何反馈。

Misha 可以按下按钮任意多次。在第一次按下按钮之前以及任意两次按下按钮之间，他可以选择任意数量的槽位，并将这些槽位中的符号（问号或数字）更改为任何其他符号。有一个限制：每更换一个符号，Misha 都必须支付一卢布。他不希望惹妈妈生气，所以他试图花费尽可能少的钱。请问保证能够获胜最少需要花费多少钱？

输入格式

第一行包含一个整数 $T$，表示测试用例的数量（$1 \le T \le 10^4$）。接下来是 $T$ 个测试用例的描述。

每个测试用例的第一行包含 $k$，即槽位的数量（$1 \le k \le 5$）。第二行包含一个长度为 $10^k$ 的二进制序列 $s$。对于每个 $i \in \{0, 1, \dots, 10^k - 1\}$，值 $s_i = 0$ 表示数字 $i$ 不可能是秘密字符串，$s_i = 1$ 表示数字 $i$ 在说明书中是被允许的，且可能被机器存储。至少存在一个 $i$ 使得 $s_i = 1$。

所有字符串的总长度不超过 $10^5$。

输出格式

输出一个整数：保证 Misha 获胜所需的最少金额（以卢布为单位）。

样例

输入 1

2
1
1110001010
1
1111111111

输出 1

3
4