题目描述

「即使执政官再圆，也不是我子民的样子！」——西瓜王

xgw 为了见到真正的西瓜，来到了小镇著名的水果店「香果屋」。他在这里看到了很多又大又圆的西瓜，他决定带几个西瓜回家。「香果屋」里有 $n$ 种西瓜，每种西瓜有一个权值 $x_i$，而有钱任性的 xgw 把每种西瓜都买了一个带回家！！

将西瓜带回家后，xgw 自然是要向他们的子民训话。每次他会从中选出一个子集进行训话，每次训话的愉悦度是选出西瓜的权值的最小公倍数乘最大公约数。

他是个任性的国王，他会把每种可以选择的方式都来一遍，当然，每次选择至少选出一个西瓜（也就是不会为空集）。

你需要求的是 xgw 训话完之后的愉悦值之和。由于答案可能过大，请输答案 $ans\mod 10^5$ 的值。

输入格式

本题有多组数据。

第一行包含一个整数 $T$, 代表测试数据的组数。

接下来是 $T$ 组测试数据，对每一组测试数据：

第一行包含一个整数 $n$, 代表元素的个数。

第二行包含 $n$ 个用空格隔开的互不相同的正整数 $x_i$。

输出格式

对每组测试数据，在新的一行输出答案。

样例

2
2
2 3
3
2 4 10

19
228

样例说明

第一组数据：

子集 $1$：$\{2\} \rightarrow lcm = 2, gcd = 2, lcm\times gcd = 4$

子集 $2$：$\{3\} \rightarrow lcm = 3, gcd = 3, lcm\times gcd = 9$

子集 $3$：$\{2,3\} \rightarrow lcm = 6, gcd = 1, lcm\times gcd = 6$

$ans = 4 + 9 + 6 = 19$

第二组数据：

子集 $1$：$\{2\} \rightarrow lcm = 2, gcd = 2, lcm\times gcd = 4$

子集 $2$：$\{4\} \rightarrow lcm = 4, gcd = 4, lcm\times gcd = 16$

子集 $3$：$\{10\} \rightarrow lcm = 10,gcd = 10 , lcm\times gcd = 100$

子集 $4$：$\{2,4\} \rightarrow lcm = 4, gcd = 2 , lcm\times gcd = 8$

子集 $5$：$\{4,10\} \rightarrow lcm = 20,gcd = 2 , lcm\times gcd = 40$

子集 $6$：$\{2,10\} \rightarrow lcm = 10,gcd = 2 , lcm\times gcd = 20$

子集 $7$：$\{2,4,10\} \rightarrow lcm = 20,gcd = 2 , lcm\times gcd = 40$

$ans = 4 + 16 + 100 + 8 + 40 + 20 + 40 = 228$

数据规模与约定

对于 $100\%$ 的数据：$1\le T\le 400$，$2\le n\le 100$，$1\le x_i\le 250$。