该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小 \(Ψ\) 上幼儿园了，他现在正在学习数数。

如果有一个 \(2\) 进制数，小 \(Ψ\) 会数其中 \(0\) 的个数。
但是今天他看到了十六进制数，他想把这个数转换为二进制，再数 \(0\) 的个数。
但是这些十六进制数太大了，所以小 \(Ψ\) 来求助会编程的你帮他解决问题。

输入格式

本题每个测试点包含多个测试数据，对于每个测试数据：

第一行：一个整数 \(n\)，表示这个十六进制数的位数

第2行：这个十六进制数

输出格式

对于每个测试数据输出一行，输出这个数转换为二进制后 \(0\) 的个数。

注意，高位 \(0\) 不应计算在内，转换后的二进制数长度至少为 \(1\)。

输入输出样例

5
25B82
7
C3C3AC1
4
ABA9
5
F9D51
5
CFD1E
6
F55AA0
4
FF52
6
C75F30
7
CC5DED9
5
0901F

10
15
7
8
7
12
5
11
11
9

数据范围

• 对于\(20\%\)的数据，有\(n\leq10\)
• 对于\(40\%\)的数据，有\(n\leq10^3\)
• 对于\(100\%\)的数据，有\(n\leq10^7\)，每个测试点中测试数据组数 \(\leq10\)