香果屋

时间限制:10s    【提交】    空间限制:1024MB

题目描述

“即使执政官再圆,也不是我子民的样子!”——西瓜王
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<=T<=400, 2<=n<=100, 1 <= x_i <= 250

第一组数据:
子集 1 : {2} ==> lcm = 2, gcd = 2, lcm*gcd = 4
子集 2 : {3} ==> lcm = 3, gcd = 3, lcm*gcd = 9
子集 3 : {2,3} ==> lcm = 6, gcd = 1, lcm*gcd = 6
答案 = 4 + 9 + 6 = 19
第二组数据:
子集 1 : {2} ==> lcm = 2, gcd = 2, lcm*gcd = 4
子集 2 : {4} ==> lcm = 4, gcd = 4, lcm*gcd = 16
子集 3 : {10} ==> lcm = 10,gcd = 10 , lcm*gcd = 100
子集 4 : {2,4} ==> lcm = 4, gcd = 2 , lcm*gcd = 8
子集 5 : {4,10} ==> lcm = 20,gcd = 2 , lcm*gcd = 40
子集 6 : {2,10} ==> lcm = 10,gcd = 2 , lcm*gcd = 20
子集 7 : {2,4,10} ==> lcm = 20,gcd = 2 , lcm*gcd = 40
答案 = 4 + 16 + 100 + 8 + 40 + 20 + 40 = 228 


题目来源

没有写明来源