You have been given a set of rectangular and square tiles. Your job is to try and put this set of tiles together to form larger rectangles. The rectangles must be completely filled in. They can't be hollow and they can't contain any holes. You have to use all of the tiles you have been given for each larger rectangle you form.

The input will contain ~10~ test cases. The first line of each test case will consist of a single integer ~N~ on a line by itself ~(1 \le N \le 10)~. This will be followed by ~N~ lines, each containing two integers ~S_1~ and ~S_2~ representing the two side lengths of one of your tiles in centimetres ~(1 \le S_1, S_2 \le 5)~. The total area of all the tiles combined for each test case will be no more than ~30~ square centimetres.

For each test case you should output a single integer representing the largest perimeter it is possible to create with the tiles when you make rectangles following the rules set out above. If it is not possible to create any rectangles with the tiles you have been given, you should output the words Not Possible with both words capitalized.

Note that the sample input below only contains ~3~ test cases, but the real data files will contain ~10~.

Sample Input

3
3 2
2 2
1 2
4
1 1
1 1
1 1
1 1
3
3 2
1 1
1 3

Sample Output

16
10
Not Possible

Question Development Team

Sam Scott (Sheridan College)
Kevin Forest (Sheridan College)
Greg Reid (St. Francis Xavier Secondary School, Mississauga)
Dino Baron (University of Waterloo)
John Ketelaars (ECOO-CS Communications)
David Stermole (ECOO-CS President)
Thanks also to Lukasz Wawrzyniak (Sheridan College)

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org