{"raw_statement":[{"iden":"statement","content":"某国有 $n$ 座城市，其中 $\\forall 1 \\leq i < n$，城市 $i$ 与城市 $i + 1$ 有**双向**道路相连。\n\n该国发生了疫情，一个城市要么无人感染，要么全体感染。具体地，一个城市初始时被感染当且仅当 $s_i = 1$。\n\n疫情会扩散，每一天上午，你可以为一个未感染的城市的居民接种疫苗，下午，每个被感染的城市会向相邻的城市扩散，如果相邻的城市未接种疫苗，它将立即全员感染。\n\n你作为城市管理者，想要知道执行最优策略的情况下，最少会有几个城市的所有人都被感染。"},{"iden":"input","content":"**本题有多组测试数据。**\n\n第一行一个整数 $T$，表示数据组数。\n\n对于每组数据：\n\n第一行，一个整数 $n$；\n\n第二行，一个长度为 $n$ 的字符串 $s$。"},{"iden":"output","content":"对于每组数据：\n\n一行，一个整数，表示所求的值。"},{"iden":"note","content":"#### 样例 #1 解释\n测试点一：第一天接种城市 $7$，第二天接种城市 $1$。\n\n测试点二：第一天接种城市 $5$，第二天接种城市 $7$。\n\n测试点三：初始不存在疫情，因此不需要接种。\n#### 数据范围\n对于 $100\\%$ 的数据，$1 \\leq n, T \\leq 10^5$，$1 \\leq \\sum n \\leq 10^6$。"}],"translated_statement":null,"sample_group":[["3\n8\n00110100\n10\n1001000010\n4\n0000","5\n7\n0"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}