Transform

A list of $n$ integers are given. For an integer $x$ you can do the following operations:

+ let the binary representation of $x$ be $\overline{b_{31}b_{30}...b_0}$, you can flip one of the bits.
+ let $y$ be an integer in the list, you can change $x$ to $x \oplus y$, where $\oplus$ means bitwise exclusive or operation.

There are several integer pairs $(S, T)$. For each pair, you need to answer the minimum operations needed to change $S$ to $T$.

There are multiple test cases. The first line of input contains an integer $T$ $(T \le 20)$, indicating the number of test cases. For each test case:

The first line contains two integer $n$ and $m$ $(1 \le n \le 15, 1 \le m \le 10^5)$ -- the number of integers given and the number of queries. The next line contains $n$ integers $a_1, a_2, ..., a_n$ $(1 \le a_i \le 10^5)$, separated by a space.

In the next $m$ lines, each contains two integers $s_i$ and $t_i$ $(1 \le s_i, t_i \le 10^5)$, denoting a query.

For each test cases, output an integer $S=(\displaystyle\sum_{i=1}^{m} i \cdot z_i) \text{ mod } (10^9 + 7)$, where $z_i$ is the answer for $i$-th query.

1
3 3
1 2 3
3 4
1 2
3 9

10

$3 \to 4$ (2 operations): $3 \to 7 \to 4$

$1 \to 2$ (1 operation): $1 \oplus 3 = 2$

$3 \to 9$ (2 operations): $3 \to 1 \to 9$

BestCoder Round #74 (div.2)