Exact Spending Challenge

You are given a set of item prices and a target amount of money. Your task is to determine whether it is possible to spend exactly the target amount by purchasing one or more items, where each item can be bought any number of times. Formally, given a list of prices \(P = [p_1, p_2, \dots, p_n]\) and a target amount \(T\), decide if there exist non-negative integers \(x_1, x_2, \dots, x_n\) (with at least one \(x_i > 0\)) such that

$$p_1 x_1 + p_2 x_2 + \cdots + p_n x_n = T.$$

This is essentially an unbounded knapsack (or coin change) problem. Good luck!

inputFormat

The input is read from standard input (stdin) and has the following format:

1. An integer \(T\) representing the number of test cases.
2. For each test case:
   • The first number is an integer \(n\) -- the number of available items.
   • Followed by \(n\) space separated integers, representing the prices of the items.
   • Followed by an integer \(T\) (target amount) that you must exactly spend.

All values are provided in a single stream of input.

outputFormat

For each test case, output a single line to standard output (stdout) with the word Possible if it is possible to exactly match the target amount using the available items, or Not Possible otherwise.

## sample

2
3 1 3 5 11
4 1 2 3 4 7

Possible
Possible

</p>