你是一个富有的人，你觉得你的钱包现在太沉、太满了。所以你想通过从我这里购买一张可爱的 Pusheen 贴纸来给我一些钱，贴纸的价格为 $p$ 美元。为了让你的钱包变轻，你决定用尽可能多的硬币和/或纸币支付恰好 $p$ 美元。

例如，如果 $p = 17$，你拥有两个 10 美元硬币、四个 5 美元硬币和八个 1 美元硬币，你将用两个 5 美元硬币和七个 1 美元硬币来支付。但由于你太富有，贴纸太贵，而且 Pusheen 太可爱了，这个任务变得极其困难，请编写一个程序来计算最佳方案。

输入格式

第一行包含一个整数 $T$，表示测试用例的总数。每个测试用例占一行，包含 11 个整数 $p, c_1, c_5, c_{10}, c_{20}, c_{50}, c_{100}, c_{200}, c_{500}, c_{1000}, c_{2000}$，分别指定了 Pusheen 贴纸的价格，以及钱包中每种面值的硬币和纸币的数量。数字 $c_i$ 表示钱包中面值为 $i$ 美元的硬币/纸币的数量。

• $1 \le T \le 20000$
• $0 \le p \le 10^9$
• $0 \le c_i \le 100000$

输出格式

对于每个测试用例，请输出支付恰好 $p$ 美元时所能使用的硬币和/或纸币的最大数量。如果无法恰好支付 $p$ 美元，请输出 ‘-1’。

样例

输入 1

3
17 8 4 2 0 0 0 0 0 0 0
100 99 0 0 0 0 0 0 0 0 0
2015 9 8 7 6 5 4 3 2 1 0

输出 1

9
-1
36