A-scx 的散文诗句_华中农业大学第十三届程序设计竞赛（同步赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

回忆总是这样，不经意的一阵风起，拨动了心弦，扑面而来的心绪，淹没了周遭的喧闹。

秋日微雨的黑夜里，路灯下昏黄的剪影，漫漫林径的尽头，我在喃喃低语，诉说着光阴的故事。

“时光总是不停流动，每一份回忆都是用心收藏。”

scx 又想写诗了。scx 一共有 $n$ 个词汇，每个词汇都有着一定的魅力值。scx 需要将这 $n$ 个词汇分成 $\lceil n/2 \rceil$ 个词组，每个词组至多有 $2$ 个词汇。

每一个有 $2$ 个词汇的词组都会让叶璃浅产生大小为该词组中的 $2$ 个词汇的魅力值的乘积的心动值。scx 想获得叶璃浅的青睐，所以他想请你帮他最大化所有产生的心动值之和。

形式化地说，你需要将 $n$ 个数分成 $\lceil n/2 \rceil$ 组，每组至多 $2$ 个数。定义你的得分为每个有 $2$ 个数的组组内两个数的乘积的和。请最大化得分。

输入描述:

每个测试点含有多组测试数据。

首先输入一个整数 ，代表测试数据组数。

对于每一组测试数据，首先输入一行一个整数 ，代表 scx 的词汇数量。

接着输入一行  个整数 ，表示每个单词的魅力值。

保证对于单个测试点， 。

输出描述:

输出  行，每行一个整数表示你的答案。

示例1

输入

复制

输出

复制

2
14

备注:

 表示向上取整，即不小于  的最小整数。例如 ，，。