CA喜欢是一个热爱党和人民的优秀同♂志，所以他也非常喜欢GCD（请在输入法中输入GCD得到CA喜欢GCD的原因）。 现在他有N个不同的数，每次他会从中选出若干个（至少一个数），求出所有数的GCD然后放回去。 为了使自己不会无聊，CA会把每种不同的选法都选一遍，CA想知道他得到的所有GCD的和是多少。 我们认为两种选法不同，当且仅当有一个数在其中一种选法中被选中了，而在另外一种选法中没有被选中。
第一行 $T$，表示有 $T$ 组数据。 接下来 $T$ 组数据，每组数据第一行一个整数 $N$，表示CA的数的个数，接下来一行 $N$ 个整数 $A_i$ 表示CA的每个数。 $1 \le T \le 50,~1 \le N \le 1000,~1 \le A_i \le 1000$
对于每组数据输出一行一个整数表示CA所有的选法的GCD的和对 $100000007$ 取模的结果。
2 2 2 4 3 1 2 3
8 10