|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
Jack and Mary usually compete one against each other. This time, Mary brought a new mobile phone to brag about her cute unlock pattern. Mary is always looking a way to compete with Jack. This time, she asked Jack how many patterns he thinks could be made with her mobile phone.
Jack looked very carefully at the phone and noticed some defective keys that cannot be used to create a pattern.
Mary kindly explained to Jack the constraints of the patterns she is interested in:
- A pattern may start at any non-damaged key and continue moving freely to any key.
- The user can slide over a defective key, but it will not contribute to the current pattern.
- To go to the next key in the pattern, the user MUST slide his finger in a straight line.
- A non-damaged key can be used only once to contribute to the pattern, i.e. once the user slides his finger over the key the first time, this key will not contribute anymore to the pattern even if the user slides again his finger over this key.
- The pattern ends whenever the user lifts his finger off the screen or there are no more non-damaged keys available to slide over.
- Two patterns, P and Q, are different if they have different lenghts or there is an index i such that $P_i \neq Q_i$.
Jack asked your help in this task to avoid losing against Mary in this new competition. Given the phone description, you must compute how many patterns can be created using the non-defective keys of the keyboard.
Input
The first line contains an integer $T \leq 1000$ representing the the number of keyboards to be analyzed. The following $3 \times T$ lines contain information about the mobile keyboards. Each keyboard will be represented as a $3 \times 3$ matrix with symbols X and $.$, where the symbol X represents a damaged key and the symbol $.$ represents a working key.
Output
The ouput contains $T$ lines with the number of patterns that can be created for each mobile keyboard given in the input.
Sample test(s)
Input
6
XXX
X.X
XXX
..X
XXX
XXX
.X.
XXX
X.X
...
XXX
XXX
X.X
.X.
X.X
..X
X.X
...
Output
1
4
15
11
64
1168
Hints
Consider the following example to have a more clear understanding of the problem. Let's number the keys as a numeric keyboard from 1 to 9 starting at the top left corner and ending at the bottom right corner. If the user makes the move $1 \rightarrow 3$, the pattern generated is $1 \rightarrow 2 \rightarrow 3$ unless key $2$ is defective or used before in the current pattern).
In the fourth example, if the user wants to go from key $1$ to key $3$, he must go in a straight line passing through key $2$, therefore the pattern $1 \rightarrow 3 \rightarrow 2$ is impossible to achieve.