清楚姐姐的布告规划
题号：NC276622
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

\,\,\,\,\,\,\,\,\,\,待榜之期，漫长如年。为自己和竹鼠们的生计，清楚在京师寻得一份张贴布告之差事，既可糊口，亦广交良朋，共商寻宝大业。 
\,\,\,\,\,\,\,\,\,\,某日，清楚在张贴布告时，浆糊不慎落于羊皮卷上，湿透之处，竟现复杂图形……
\,\,\,\,\,\,\,\,\,\,清楚需要在长度为 n 个单位的布告板上张贴至多 n 张布告，第 i 张布告的长度为 a_i 个单位，如果选择第 i 张贴布告时需要满足：
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 第 i 张布告必须要覆盖掉布告板的第 i 个位置；
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 布告不能够相互重叠，但是可以紧贴。
\,\,\,\,\,\,\,\,\,\,清楚想要知道自己按照要求，至少需要张贴几张布告，才能将布告板贴满。

输入描述:

\,\,\,\,\,\,\,\,\,\,每个测试文件均包含多组测试数据。第一行输入一个整数 T\ (1\le T\le 100) 代表数据组数，每组测试数据描述如下：
\,\,\,\,\,\,\,\,\,\,第一行输入一个整数 n\ (1 \leq n \leq 5000) 代表布告板的长度（同时也代表布告的张数）。
\,\,\,\,\,\,\,\,\,\,第二行输入 n 个整数 a_1,a_2,\dots,a_n\ (1 \leq a_i \leq n) 代表每一张布告的长度。
\,\,\,\,\,\,\,\,\,\,除此之外，保证所有的 n 之和不超过 5000 。

输出描述:

\,\,\,\,\,\,\,\,\,\,对于每一组测试数据，在一行上输出一个整数代表清楚至少需要贴的布告数量；如果无解，直接输出 -1 。
示例1

输入

复制 
2
4
1 2 2 3
3
2 2 2

输出

复制 
2
-1

说明

\,\,\,\,\,\,\,\,\,\,对于第一组测试数据，有两种合法的选择方式：
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 贴第一、四张布告；
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 贴第二、三张布告；
\,\,\,\,\,\,\,\,\,\,对于第二组测试数据，无论怎么张贴都会有重叠部分。