Transform

给出$n$个整数, 对于一个整数$x$, 你可以做如下的操作若干次:

  + 令$x$的二进制表示为$\overline{b_{31}b_{30}...b_0}$, 你可以翻转其中一个位.
  + 令$y$是给出的其中一个整数, 你可以把$x$变为$x \oplus y$, 其中$\oplus$表示位运算里面的异或操作.

现在有若干整数对$(S, T)$, 对于每对整数你需要找出从$S$变成$T$的最小操作次数.

输入包含多组数据. 第一行有一个整数$T$ $(T \le 20)$, 表示测试数据组数. 对于每组数据:

第一行包含两个整数$n$和$m$ $(1 \le n \le 15, 1 \le m \le 10^5)$, 表示给出整数的数目和询问的数目. 接下来一行包含$n$个用空格分隔的整数$a_1, a_2, ..., a_n$ $(1 \le a_i \le 10^5)$.

接下来$m$行, 每行包含两个整数$s_i$和$t_i$ $(1 \le s_i, t_i \le 10^5)$, 代表一组询问.

对于每组数据, 输出一个整数$S=(\displaystyle\sum_{i=1}^{m} i \cdot z_i) \text{ mod } (10^9 + 7)$, 其中$z_i$是第$i$次询问的答案.

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

10

$3 \to 4$ (2次操作): $3 \to 7 \to 4$

$1 \to 2$ (1次操作): $1 \oplus 3 = 2$

$3 \to 9$ (2次操作): $3 \to 1 \to 9$