## GRSEQ - Graphic Sequence

Given an integer sequence d = (d1, . . . , dn) determine if there exists a graph G with permutation of d as its sequence of degrees.

### Input

The input consists of a sequence of lines. In the first line you are given t<100 - the number of sequences to analyze. The description of each of the sequences consists of two lines: in the first line you are given one number n<=100000 (the length of the sequence) and in the second line you are given n nonnegative integers (the sequence elements, all of these numbers are smaller than 100000).

### Output

For each of the sequences print in a separate line one of the two words: POSSIBLE if such a graph might exists and IMPOSSIBLE in the opposite case.

### Example

```Input:
4
3
1 2 2
4
3 2 3 2
5
2 2 4 2 2
4
0 0 0 0

Output:
IMPOSSIBLE
POSSIBLE
POSSIBLE
POSSIBLE
```

### Input data sizes

``` t    maxn      l
1    10        0.4s
2    100       0.4s
3    1000      0.4s
4    10000     0.4s
5    100000    0.4s

t    - testcase number
maxn - the maximum length of the sequence
l    - time limit
```

### Hints

Using the Erdős–Gallai Theorem you will be able to implement a linear time algorithm.

You could try also Social Network Existence - very similar problem with smaller inputs.