#P18299. Slot Machine

Slot Machine

Slot Machine

小 Misha 正坐在一台老虎机前,希望赢得大奖。机器有 kk 个按顺序排列的显示位,每一位可以显示一个十进制数字或问号。最初,所有位置都显示问号。

机器内部藏有一个长度为 kk 的十进制字符串,可能带有前导零。Misha 找到了机器的说明书,其中列出了所有可能藏在机器中的字符串;说明书之外的字符串不会成为秘密字符串。

为了赢得大奖,Misha 必须使屏幕显示的 kk 个字符与秘密字符串完全相同,并按下红色按钮。若按按钮时屏幕是一个完整的数字串、但与秘密字符串不同,机器会把两者转换为整数,告诉他哪一个更大;允许存在前导零。若屏幕上还有问号,机器不会提供任何信息。

按按钮免费,次数不限。在第一次按按钮之前,以及相邻两次按按钮之间,Misha 可以任选若干位置,把这些位置上的符号替换为任意数字或问号;每替换一个位置上的符号,需要支付 1 卢布。

屏幕上的猜测数字不必出现在说明书中。Misha 可以根据机器之前提供的信息决定后续操作。求无论秘密字符串是哪一个,保证最终获胜所需支付金额的最小值。

输入格式

第一行包含测试用例数 TT,满足 1≤T≤1041≤T≤10^4。

每个测试用例占两行:

  • 第一行包含整数 kk,满足 1≤k≤51≤k≤5。
  • 第二行包含长度恰为 10k10^k 的 01 串 ss。按从左到右的顺序,将其字符编号为 0,1,…,10k−10,1,\ldots,10^k-1:si=1s_i=1 表示整数 ii 对应的、补足前导零后的 kk 位数字串可能是秘密字符串;si=0s_i=0 表示不可能。

每个 ss 至少包含一个 1。全部测试用例中 ss 的长度之和不超过 10510^5。

输出格式

对每个测试用例,输出一个整数,表示能保证获胜的最小支付金额。

样例

输入:

2
1
1110001010
1
1111111111

输出:

3
4