A Jigsaw puzzle contains N*M-1 pieces of jigsaws in a N rows*M columns rectangular board.Each jigsaw has a distinct number from 1 to N*M-1.Li is a naughty boy,he wants to arrange the board in his unique way.At the beginning,he picks all N*M-1 jigsaws out and put them on the table and then he will put them back to the board respecting the following steps:

1.Sorting all the remaining jigsaws on the table in ascending order.

2.Picking out the 1st ,the P+1 th ,the 2*P+1 th,......the n*P+1 th jigsaws and put them back to the blank area in the board one by one from the top row to the bottom row,from the left column to the right column.

3.if there are jigsaws remained on the table,back to step 1.

After he arranging the board,it’s obvious that there’s only one blank area located at the bottom-right corner.

Your task is to make the numbers on jigsaws sorted with every row and every column in ascending order(From left to right,top to bottom),and the blank area should be located at the bottom-right corner in the end.Each step you can move the blank area’s neighboring jigsaws(which share a common side with the blank area) towards the blank area.It’s really a difficult question,so you need to write a program to judge whether it is possible to complete the task.

1.Sorting all the remaining jigsaws on the table in ascending order.

2.Picking out the 1st ,the P+1 th ,the 2*P+1 th,......the n*P+1 th jigsaws and put them back to the blank area in the board one by one from the top row to the bottom row,from the left column to the right column.

3.if there are jigsaws remained on the table,back to step 1.

After he arranging the board,it’s obvious that there’s only one blank area located at the bottom-right corner.

Your task is to make the numbers on jigsaws sorted with every row and every column in ascending order(From left to right,top to bottom),and the blank area should be located at the bottom-right corner in the end.Each step you can move the blank area’s neighboring jigsaws(which share a common side with the blank area) towards the blank area.It’s really a difficult question,so you need to write a program to judge whether it is possible to complete the task.

The first line contains an integer T(T<=100),which represents the number of test cases.

Following T lines,each line contains three integers N,M,P(2<=N,M<=1000;1<=P<=N*M-2).

Following T lines,each line contains three integers N,M,P(2<=N,M<=1000;1<=P<=N*M-2).

提交代码