#P18299. Slot Machine
Slot Machine
Slot Machine
小 Misha 正坐在一台老虎机前,希望赢得大奖。机器有 个按顺序排列的显示位,每一位可以显示一个十进制数字或问号。最初,所有位置都显示问号。
机器内部藏有一个长度为 的十进制字符串,可能带有前导零。Misha 找到了机器的说明书,其中列出了所有可能藏在机器中的字符串;说明书之外的字符串不会成为秘密字符串。
为了赢得大奖,Misha 必须使屏幕显示的 个字符与秘密字符串完全相同,并按下红色按钮。若按按钮时屏幕是一个完整的数字串、但与秘密字符串不同,机器会把两者转换为整数,告诉他哪一个更大;允许存在前导零。若屏幕上还有问号,机器不会提供任何信息。
按按钮免费,次数不限。在第一次按按钮之前,以及相邻两次按按钮之间,Misha 可以任选若干位置,把这些位置上的符号替换为任意数字或问号;每替换一个位置上的符号,需要支付 1 卢布。
屏幕上的猜测数字不必出现在说明书中。Misha 可以根据机器之前提供的信息决定后续操作。求无论秘密字符串是哪一个,保证最终获胜所需支付金额的最小值。
输入格式
第一行包含测试用例数 ,满足 。
每个测试用例占两行:
- 第一行包含整数 ,满足 。
- 第二行包含长度恰为 的 01 串 。按从左到右的顺序,将其字符编号为 : 表示整数 对应的、补足前导零后的 位数字串可能是秘密字符串; 表示不可能。
每个 至少包含一个 1。全部测试用例中 的长度之和不超过 。
输出格式
对每个测试用例,输出一个整数,表示能保证获胜的最小支付金额。
样例
输入:
2
1
1110001010
1
1111111111
输出:
3
4