Minimum Number of Plates

You are given several types of plates, each with a specific weight. Your task is to determine the minimum number of plates required to exactly reach a target weight \(W\). You have an unlimited supply of each type of plate.

If it is impossible to form the weight exactly, you should output \(-1\).

Example: For plate types with weights [1, 3, 4] and a target weight of 6, one optimal solution is to use two plates with weight 3 each, so the answer is 2.

inputFormat

The input is given from standard input (stdin) and consists of multiple test cases. The first line of input contains an integer \(T\), the number of test cases. Each test case is described as follows:

• The first line contains an integer \(n\), the number of plate types.
• The second line contains \(n\) space-separated integers representing the weights of each plate type.
• The third line contains an integer \(W\), the target weight that needs to be formed exactly.

outputFormat

For each test case, output a single line to standard output (stdout) containing the minimum number of plates required to form exactly \(W\). If it is not possible, output \(-1\).

## sample

3
3
1 3 4
6
2
2 5
3
4
1 2 3 4
7

2
-1
2

</p>