Even Sum Pairs Reordering

You are given a sequence of n integers. Your task is to determine if it is possible to rearrange the sequence in such a way that the sum of every pair of adjacent numbers is even.

Recall that the sum of two numbers is even if both numbers are even or both are odd. Thus, for the sequence to be re-arranged accordingly, the number of odd elements must be even (including zero), so that they can be paired among themselves. If this condition is met, output "Possible"; otherwise, output "Not Possible".

The input consists of multiple test cases. Each test case begins with an integer n (the length of the sequence), followed by a line with n integers separated by spaces. The input ends when n is 0, which should not be processed.

Example:
Input:
4
2 4 6 8
5
1 2 3 4 5
3
1 3 5
4
1 3 5 7
0

Output:
Possible
Not Possible
Not Possible
Possible

inputFormat

The input is read from stdin and consists of multiple test cases. Each test case is described as follows:

• The first line contains an integer n (1 ≤ n ≤ 10⁵ or as constrained by the problem). If n is 0, it marks the end of input.
• The second line contains n space-separated integers representing the sequence.

Multiple test cases appear one after the other.

outputFormat

For each test case, output a single line containing "Possible" if the sequence can be rearranged such that every adjacent pair sums to an even number; otherwise, output "Not Possible". The output is written to stdout.

## sample

4
2 4 6 8
0

Possible

</p>