Description

欢迎进入“挂羊头，卖狗肉”专柜下面继续

给定1个数m和n个数{a1，a2，...,an},那么请问，最少需要从这n个数中选出多少个，使这些数之和恰好等于m？

Input

首先一个整数cas,表示接下来由cas个数据 每组数据第一行两个整数m,n(1<=m<=100,1<=n<=10) 第二行包含n个整数,表示数组a, 每个整数在[1,10]之间

Output

如果有满足条件的选法，输出最少需要选出的个数.否则,输出-1 每组输出占一行.

Sample

Input

2
32 10
3 10 5 2 6 6 8 1 9 8
76 7
9 1 10 7 3 4 8

Output

4
-1

Hint

第一组数据选取{10,6,8,8} ，第二组数据无解。