Given an 8 x 8 chess board where 8 queens are placed in any arbitrary order. You want to move the queens such that no one attacks each other.
In each move you can move a queen as in normal chess. That means you can move a queen vertically, horizontally or diagonally. And you can move it to multiple cells at a time but the direction can't be changed and you can't jump over any other queen. Now you want to find the minimum number of moves to do this.
Input
Input starts with an integer T (≤ 200), denoting the number of test cases.
Each case contains a blank line and an 8 x 8 board consisting of '.' and exactly eight 'q'. '.' stands for empty position and 'q' stands for a queen.
Output
For each case, output the case number and minimum number of queen moves you have to do such that no queen attacks another.
Sample
| Sample Input | Sample Output |
|---|---|
2 q....... .q...... ..q..... ...q.... ....q... .....q.. ......q. .......q .......q .......q ........ ...q..q. .q...q.. ....q... ..q..... ........ | Case 1: 7 Case 2: 5 |
