The Oculus

Let's define the Fibonacci sequence $F_1,F_2,\dots$ as $F_1=1,F_2=2,F_i=F_{i-1}+F_{i-2}$ ($i\geq 3$).

It's well known that every positive integer $x$ has its unique Fibonacci representation $(b_1,b_2,\dots,b_n)$ such that:

· $b_1\times F_1+b_2\times F_2+\dots+b_n\times F_n=x$.

· $b_n=1$, and for each $i$ ($1\leq i<n$), $b_i\in\{0,1\}$ always holds.

· For each $i$ ($1\leq i<n$), $b_i\times b_{i+1}=0$ always holds.

For example, $4=(1,0,1)$, $5=(0,0,0,1)$, and $20=(0,1,0,1,0,1)$ because $20=F_2+F_4+F_6=2+5+13$.

There are two positive integers $A$ and $B$ written in Fibonacci representation, Skywalkert calculated the product of $A$ and $B$ and written the result $C$ in Fibonacci representation. Assume the Fibonacci representation of $C$ is $(b_1,b_2,\dots,b_n)$, Little Q then selected a bit $k$ ($1\leq k<n$) such that $b_k=1$ and modified $b_k$ to $0$.

It is so slow for Skywalkert to calculate the correct result again using Fast Fourier Transform and tedious reduction. Please help Skywalkert to find which bit $k$ was modified.

The first line of the input contains a single integer $T$ ($1 \leq T \leq 10\,000$), the number of test cases.

For each case, the first line of the input contains the Fibonacci representation of $A$, the second line contains the Fibonacci representation of $B$, and the third line contains the Fibonacci representation of modified $C$.

Each line starts with an integer $n$, denoting the length of the Fibonacci representation, followed by $n$ integers $b_1,b_2,\dots,b_n$, denoting the value of each bit.

It is guaranteed that:

· $1\leq |A|,|B|\leq 1\,000\,000$.

· $2\leq |C|\leq |A|+|B|+1$.

·$\sum |A|,\sum |B|\leq 5\,000\,000$.

For each test case, output a single line containing an integer, the value of $k$.

1
3 1 0 1
4 0 0 0 1
6 0 1 0 0 0 1

4

2020 Multi-University Training Contest 2