小苯的糖果盒

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

题目描述

$\hspace{15pt}$ 小苯有 $n$ 个盒子排成一排，第 $i$ 个盒子初始装有 $a_i$ 颗糖果。
$\hspace{15pt}$ 他可以进行以下操作任意次：选择两个不同的盒子 $i$ 和 $j$ ，将盒子 $i$ 中的一颗糖果移动到盒子 $j$ 。移动的成本为 $|i-j|$ （即两个盒子的位置距离）。

$\hspace{15pt}$ 小苯希望最终满足以下条件：
$\hspace{23pt}\bullet\,$ 每个盒子中的糖果数量都是一个完全平方数；
$\hspace{23pt}\bullet\,$ 所有盒子的糖果数量构成一个非递减序列（即 $b_1 \leqq b_2 \leqq \dots \leqq b_n$ ，其中 $b_i$ 是第 $i$ 个盒子最终的数量）。
$\hspace{15pt}$ 请帮助他计算所需的最小总成本，或报告无解。

【名词解释】
$\hspace{15pt}$ 完全平方数：一个数如果可以表示为某个整数的平方，那么这个数就是完全平方数。前十个完全平方数是 $0,1,4,9,16,25,36,49,64,81$ 。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数 。
第二行输入  个整数 。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每组数据，输出一个整数，表示满足条件的最小总成本，如果无法做到，输出一个 。

示例1

输入

复制

输出

复制

5
-1

说明

对于第一组测试数据，最优方案是最终序列 （全是完全平方数且非递减），总成本为 。