题目描述
Liji 在游戏中对抗一个Boss，Boss 的血条由 n 段组成，其中每一段的血量为 1，2，……，n。
对抗该 Boss 按照以下特殊方式（可使用任意次，可以为 0 次）：
· 选择一个正整数 k（1 ≤ k ≤ n），如果剩余血条中存在血量为 k 的倍数，则使 Boss 失去血量为 x 的那一段血条，x 为当前 Boss 存在的血条血量中 k 的最小倍数，并且消耗 k 点法力值
由于 Liji 喜欢在游戏里整活，他给定你一个血条分布情况，你需要求出最初的 Boss 血条变为给定状态所消耗的最小法力值。
对抗该 Boss 按照以下特殊方式（可使用任意次，可以为 0 次）：
· 选择一个正整数 k（1 ≤ k ≤ n），如果剩余血条中存在血量为 k 的倍数，则使 Boss 失去血量为 x 的那一段血条，x 为当前 Boss 存在的血条血量中 k 的最小倍数，并且消耗 k 点法力值
由于 Liji 喜欢在游戏里整活，他给定你一个血条分布情况，你需要求出最初的 Boss 血条变为给定状态所消耗的最小法力值。
输入
第一行包含一个整数 t（1 ≤ t ≤ 1e4），代表有 t 个测试样例。
对于每个测试样例：
第一行包含一个整数 n（1 ≤ n ≤ 1e6）。
第二行包含一个长度为 n 的二进制字符串，描述 Liji 给定的血条分布情况，第 i 个字符为 1 时代表血量为 i 的血条存在，为 0 时代表血量为 i 的血条不存在。
数据保证 n 的总和不超过 1e6。
对于每个测试样例：
第一行包含一个整数 n（1 ≤ n ≤ 1e6）。
第二行包含一个长度为 n 的二进制字符串，描述 Liji 给定的血条分布情况，第 i 个字符为 1 时代表血量为 i 的血条存在，为 0 时代表血量为 i 的血条不存在。
数据保证 n 的总和不超过 1e6。
输出
每个测试样例输出占一行，包含一个整数，代表最初的 Boss 血条变为给定状态所消耗的最小法力值。
样例输入 Copy
6
6
111111
7
1101001
4
0000
4
0010
8
10010101
15
110011100101100
样例输出 Copy
0
11
4
4
17
60
提示
对于测试样例一：
给定状态已经是 Boss 血条当前的状态，你不需要进行任何操作。
对于测试样例二：
Boss 血条最初为 {1，2，3，4，5，6，7}，目标是 {1，2，4，7}，你可以按照以下方式攻击：
1. 选择 k = 3，攻击 Boss 血条 3
2. 选择 k = 3，攻击 Boss 血条 6
3. 选择 k = 5，攻击 Boss 血条 5
此方案消耗的法力值为 3+3+5=11，不存在消耗法力值更小的方案。
对于测试样例三：
Boss 血条最初为 {1，2，3，4}，目标是 {}，你可以按照以下方式攻击：
只选择 k = 1，攻击 Boss 血条 1、2、3、4
此方案消耗的法力值为 1+1+1+1=4。
给定状态已经是 Boss 血条当前的状态，你不需要进行任何操作。
对于测试样例二：
Boss 血条最初为 {1，2，3，4，5，6，7}，目标是 {1，2，4，7}，你可以按照以下方式攻击：
1. 选择 k = 3，攻击 Boss 血条 3
2. 选择 k = 3，攻击 Boss 血条 6
3. 选择 k = 5，攻击 Boss 血条 5
此方案消耗的法力值为 3+3+5=11，不存在消耗法力值更小的方案。
对于测试样例三：
Boss 血条最初为 {1，2，3，4}，目标是 {}，你可以按照以下方式攻击：
只选择 k = 1，攻击 Boss 血条 1、2、3、4
此方案消耗的法力值为 1+1+1+1=4。