Rearrange Playlist

You are given a playlist consisting of N songs, where each song is represented by a character denoting its genre. Determine whether it is possible to rearrange the playlist so that no two adjacent songs have the same genre.

Formally, given a string s of length N, check if the maximum frequency of any character is less than or equal to \(\frac{N+1}{2}\). If it is, output "Possible"; otherwise, output "Not Possible".

The input begins with an integer T, the number of test cases. Each test case consists of an integer N followed by a string of length N.

inputFormat

The first line contains an integer T, the number of test cases. For each test case, there are two lines:

• The first line contains an integer N (the number of songs).
• The second line contains a string of N characters, where each character represents a genre of the song.

outputFormat

For each test case, print a single line containing "Possible" if the playlist can be rearranged such that no two adjacent songs have the same genre, otherwise print "Not Possible".

## sample

3
5
aabbc
4
aaaa
3
abc

Possible
Not Possible
Possible

</p>