Legends who were born in 90s remember Mario very well. As we all are aware of that fabulous video game our little Mario tackling with all the problems and barriers coming his way , he finally saves his Queen from the giant monster Dragon.

In this problem we let you play the game but with a little twist. The aim is same though. You have to help out our Mario to save the Queen.

Twist is that you will be given a Matrix for current stage with characters including M (Position of Mario), Q (Position of Queen), $ (Position(s) of Dragon(s)) and .(dot) (Empty Positions).

Our Mario is asking you to tell him how many different and Unique moves he can make to save the Queen and then he will request you to tell him the very Optimized move (if there any).

So if you are really a big Mario Video Game fan then help out little Mario.

Input : First line will contains integer T indicating number of Test Cases. Each Test Case will have an integer N indicating the NxN matrix. Next N lines will be having the NxN matrix.

Output : For each Test Case produce the output as follows, Case x: y < a1 a2 ... an > where x : Test Case Number, y : Optimized Step and < a1 a2 ... an > array in increasing order of all possible steps he can play.

Note : If there is no move to save the Queen just print -1.

Constraints

1<= T <= 10

3<= N <= 10

Note :- To be Eligible for Prizes you have to register and create your home address maptag.

Click here to create your Maptag