题目描述

在美好的暑假，囧囧参加了补习班。有一天老师给同学们布置了一项作业：

对于一个非负整数 $n$，$b_n$ 表示 $N$ 的二进制表示中 $1$ 的格式奇偶性（当 $n$ 的二进制中有偶数个 $1$ 时 $b_n = 0$，否则 $b_n = 1$），对于 $0 \le n$，$b_n$ 形成了一个无限长的 $0/1$ 序列。给定一个长度为 $p$ 的序列 $c_0,c_1,\cdots,c_{p-1}$，请找出 $c$ 在 $b$ 中第一次出现的位置（即最小非负整数 $k$，使得存在 $0 < p$, $c_i = b_{i+k}$）。

然后老师给了同学吗一些 $p$ 很小的数列，让同学吗完成。当然老师希望同学们用电脑完成这个任务。但是囧囧认为此题过于简单，决定全部用手算出答案。

老师知道了这件事后很生气，后果很严重。因此决定单独给囧囧布置一项作业：

给定一个长度为 $p$ 的序列 $c_0,c_1,\cdots,c_{p-1}$，求出 $c$ 的每一个前缀在 $b$ 中第一次出现的位置。

当然，为了防止囧囧再次用手算出答案，老师准备了许多 $p$ 超大的数据。这下囧囧真的囧了，你能帮帮他吗？

输入格式

第一行有一个正整数 $T$,表示数据组数。

每个数据包含两行，

第一行有一个正整数 $p$，

第二行包含p个用空格隔开的 $0/1$ 序列。

输出格式

对于每个数据输出一行,如果序列在 $b$ 中不存在,则输出 -1。

样例输入

1
9
1 0 0 1 0 1 1 1 0

样例输出

1 2 4 4 8 8 8 -1 -1

提示

【样例说明】

$b$ 的前 $16$ 项为 $\{0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0\}$。

数据规模和约定

在 $20 \%$ 的数据中，$p \le 100$。

在 $100 \%$ 的数据中，$T \le 10^3$，$p \le 10^6$，单个数据中 $\sum p \le 2 \times 10^6$。

题目来源

HNOI2009 集训 Day2