题目描述

在你居住的城市 Kickstartland 中，有一条特别长的街道，街上有 $N$ 栋房子。这条街道的长度为 $N$，$N$ 栋房子均匀分布在街上，即第 $1$ 栋房子位于位置 $1$，第 $2$ 栋房子位于位置 $2$，依此类推。任意两栋房子 $i$ 和 $j$ 之间的距离为 $|i - j|$，其中 $|x|$ 表示 $x$ 的绝对值。

其中一些房子的门前有垃圾桶。这意味着这些房子的主人倒垃圾时无需行走。然而，对于门前没有垃圾桶的房子的主人，他们必须走向某个门前有垃圾桶的房子（要么向左，要么向右）。

为了节省时间，每个房子的主人总是将垃圾带到离自己房子最近的垃圾桶处。如果两个垃圾桶距离该房子一样近，则主人可以走向其中任意一个。

给定房子的数量 $N$，以及哪些房子门前有垃圾桶的描述，请计算出每个房子的主人倒垃圾所需行走的距离之和。你可以假设至少有一栋房子门前有垃圾桶。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例由两行组成。

每个测试用例的第一行包含一个整数 $N$，表示街道上房子的数量。

每个测试用例的第二行包含一个长度为 $N$ 的字符串 $S$，表示哪些房子门前有垃圾桶。如果字符串 $S$ 的第 $i$ 个字符等于 $1$，则表示第 $i$ 栋房子门前有垃圾桶；否则，如果等于 $0$，则表示第 $i$ 栋房子门前没有垃圾桶。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是每个房子的主人倒垃圾所需行走的距离之和。

2
3
111
6
100100

Case #1: 0
Case #2: 5

提示

对于第 $1$ 个测试用例，每个房子门前都有垃圾桶，因此没有房主需要行走倒垃圾。

对于第 $2$ 个测试用例，第 $1$ 栋和第 $4$ 栋房子的主人门前有垃圾桶，因此他们无需行走。第 $2$ 栋房子的主人将走向第 $1$ 栋房子，距离为 $1$。第 $3$、$5$ 和 $6$ 栋房子的主人将走向第 $4$ 栋房子，距离分别为 $1$、$1$ 和 $2$。

限制条件

$1 \le T \le 100$。

$S$ 的长度等于 $N$。

$S$ 的每个字符为 $0$ 或 $1$。

$S$ 中至少有一个字符 $1$。

测试集 1

$1 \le N \le 100$。

测试集 2

$1 \le N \le 5 \times 10^5$。

翻译由 DeepSeek V4 Pro 完成