Description

给定一个正整数序列 。定义一个序列的子序列 为 ，其中 ，现定义一个在原序列上的操作 ：在原序列中删除某一个子序列 ，变为新序列 ，记新序列为 ，定义 的价值：

求 。

特别地，如果 中只有一个元素， 。

Input Format

第一行一个正整数T(T≤5)，表示数据组数。

从第2行开始，第2T行表示包含一个正整数n，表示正整数序列的元素个数。

第2T+1行包含n个正整数 ，即正整数序列中的元素。

Output Format

共T行，每行一个正整数，表示 的值。

Sample

【输入样例】 1 3 2 6 3 【输出样例】 6

Hint

对于20%的数据，1≤n≤50；

对于40%的数据，1≤n≤200；

对于100%的数据，1≤n≤2×105，1≤ai≤2×105，保证ai互不相同。