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$.
Input
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.
Output
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.
