题目描述

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

机器内部还保存着一个由 $k$ 个十进制数字组成的秘密字符串。并不是所有长度为 $k$ 的十进制字符串都可能成为秘密字符串：Misha 在机器说明书的第 007 章中找到了所有可能的秘密字符串列表。

为了获胜，玩家需要让 $k$ 个槽位显示的字符串与秘密字符串完全相同，然后按下一个红色按钮。如果按下按钮时显示字符串与秘密字符串不同，机器会把两者都视为整数进行比较，并告诉玩家哪一个更大。注意，前导零允许存在；如果按下按钮时至少有一个槽位仍为问号，机器不会给出任何信息。

Misha 可以按任意多次按钮。在第一次按按钮前，以及任意两次按按钮之间，他都可以选择任意多个槽位，把这些槽位上的符号改成任意其他符号。这里的符号可以是问号或数字。每改动一个槽位上的符号，Misha 需要支付 $1$ 卢布。

他希望保证获胜，并尽量少花钱。请问保证获胜最少需要多少卢布。

输入格式

第一行包含一个整数 $T$，表示测试用例数。

每个测试用例包含两行。第一行包含一个整数 $k$，表示槽位数。第二行包含一个长度为 $10^k$ 的二进制串 $s$。

对于每个 $i\in\{0,1,\ldots,10^k-1\}$，若 $s_i=0$，表示数字 $i$ 不可能是秘密字符串；若 $s_i=1$，表示数字 $i$ 被说明书允许，可能被机器保存为秘密字符串。

保证每个测试用例中至少存在一个 $i$ 使得 $s_i=1$。

输出格式

对于每个测试用例，输出一行一个整数，表示保证 Misha 获胜所需的最少金额。

数据范围

• $1\le T\le 10^4$；
• $1\le k\le 5$；
• 所有测试用例中二进制串长度之和不超过 $10^5$。

样例 1

输入

2
1
1110001010
1
1111111111

输出

3
4