时间限制： 0.5 秒

空间限制： 256 MB

题目描述

林吉吉热爱数学。正巧最近林吉吉学到了集合的知识。

他想到了一些有趣的操作，对一个集合 $S$，他找到了这个集合的所有子集，再将这些子集的元素之和进行累加，他将获得的这个数叫做密集数。

给定一个集合 $S$ 请你求其密集数。

形式化来说，令 $P = C \mid C \subseteq S$，求 $\underset{C \in P}{\sum} \underset{x \in C}{\sum} x$。

输入格式

从标准输入读入数据。

第一行为数据组数 $T$。

每组数据第一行为 $n$ 表示集合中元素的个数。

第二行 $n$ 个整数 $a_{1} , a_{2} , \cdots , a_{n}$ 表示集合 $S$ 中的所有元素。

输出格式

输出到标准输出。

每组数据输出一行结果为集合的密集数。

1
2
1 3

8

子任务

对于所有数据，$1 \leq T , a_{i} \leq 1000, 0 \leq n \leq 15$，保证集合中元素各不相同。