Grid Sortedness Check

You are given one or more test cases. In each test case, there is a grid of integers with (n) rows and (m) columns. Although you are allowed to perform any number of 90\degree rotations on any 3\times3 subgrids, your task is simply to determine whether the grid is already sorted. A grid is considered sorted if every row and every column is in non-decreasing order. In other words, the grid is sorted if for every valid (i, j): [ a_{i,j} \le a_{i,j+1}, \quad \text{and} \quad a_{i,j} \le a_{i+1,j}, ] where the inequalities hold for all applicable indices. If the grid satisfies these conditions, print "Possible"; otherwise, print "Impossible".

inputFormat

The input is given from standard input (stdin). The first line contains an integer (T) representing the number of test cases. For each test case, the first line contains two integers (n) and (m) (the number of rows and columns). This is followed by (n) lines, each containing (m) integers, which represent the grid.

outputFormat

For each test case, output a single line to standard output (stdout) containing either "Possible" if the grid is sorted in both rows and columns or "Impossible" otherwise.## sample

2
3 3
1 2 3
4 5 6
7 8 9
3 4
7 5 3 1
6 4 2 8
9 0 1 3

Possible
Impossible