You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

在质数电脑事件发生后，$Alice$努力的辨认数组中的数是质数还是合数，但还是在第一个数组就判断错误了，电脑很不幸的发生了爆炸。

几天后，$Alice$在网上发现了关于这种病毒的报道，实际上需要判断输入质数的个数是否大于或等于合数的个数，$Bob$向他提供了相反的信息，$Alice$感到非常愤怒，决定报复$Bob$.(该内容仅为故事背景,,,)

$Bob$正在上高中，准备参加夜之国想象竞赛(Nightcountry contest Of Imagination，简称NOI)，一天，$Bob$参加了一场模拟赛，比赛非常顺利，还没结束就已经完成了所有题目的作答，于是他决定先去吃饭，$Alice$想修改$Bob$该场比赛的所有题目的分数，进行一些小小的恶作剧.

具体的，$Bob$的作答分为$T$个子题目，每个子题目有$n$个正整数作为其得分$a_1,a_2,...,a_n$，$Alice$决定将所有得分对$114$取模，然后将每个子题目的得分相加后输出，使得$Bob$的分数大幅度下降。

由于$Bob$的分数个数过多，而$Alice$的电脑之前发生爆炸，只好来求助你了。

Format

Input

第一行为一个整数$T$ ($1 \leq T \leq 100$)，表示共有$T$个子题目

每个子题目的第一行为一个数$n$($1 \leq n \leq 10^6$)，表示该子题目共有$n$个分数

接下来的一行有$n$个用空格隔开的数$a_i$($1 \leq a_i \leq 10^{9}$),表示每个分数

保证每个测试点的所有子题目的$n$的和不超过$10^6$.

Output

对于每个子题目，输出一个正整数,表示操作后$Bob$该子题目分数的和。

Samples

输入 #1

2
3
4 6 8
4
114514 1919810 229028 1919810

输出 #1

18
160

对于第一个子问题，4,6,8取模都为其本身，相加的和是18

对于第二个子问题，114514对114取模为58,1919810对114取模为50,1919810对114取模为2，相加的和为160

输入 #2

2
3
114 114 114
2
113 1

输出 #2

0
114

对于第一个子问题，114对114取模为0，相加的和是0

对于第二个子问题，113对114取模为113,1对114取模为1,相加的和为114

Limitation

1s, 1024KiB for each test case.

取模运算的原理基于整数除法的性质。当我们将一个数$a$除以另一个数$n$时，可以得到一个商$q$和一个余数$r$。根据除法的定义，我们有以下等式：

$a=n×q+r$

对此，我们说$a$对$n$取模为$r$

其中，$0 \leq r < n$，即余数$r$是一个非负整数，且小于除数$n$

在$c/cpp/java$中，取模的运算符为$\%$,以下为一份示例代码

r = a % n