📖 Bài giảng & lời giải: đây là Bài tập 6 trong bài giảng Thuật toán qua trò chơi 5: Cờ caro trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Tic-tac-toe được chơi trên bàn $3 \times 3$: X đi trước, hai người lần lượt đánh vào một ô trống; ai có 3 quân thẳng hàng (ngang, dọc hoặc chéo) trước thì thắng; bàn kín mà chưa ai thắng thì hoà.

Cho $T$ thế cờ, mỗi thế cờ hợp lệ (đạt được từ bàn trống theo đúng luật) và chưa kết thúc. Người tới lượt xác định bởi số quân: số X bằng số O thì tới lượt X, ngược lại tới lượt O. Với mỗi thế cờ, gọi $K$ là kết quả tốt nhất (thắng, hoà hoặc thua) mà người tới lượt chắc chắn đạt được khi cả hai cùng chơi hoàn hảo. Hãy đếm số ô trống mà nếu người tới lượt đánh vào đó (và sau đó cả hai tiếp tục chơi hoàn hảo) thì vẫn đạt đúng kết quả $K$. Không phân biệt thắng nhanh hay thắng chậm.

Dữ liệu vào

• Dòng 1: số nguyên $T$ ($1 \le T \le 1000$).
• Tiếp theo là $T$ thế cờ, mỗi thế cờ gồm 3 dòng, mỗi dòng là một xâu 3 ký tự X, O, ..

Kết quả

In ra $T$ dòng, dòng thứ $j$ là đáp án của thế cờ thứ $j$.

Sample Input

3
...
...
...
XOX
.O.
X.O
XO.
...
...

Sample Output

9
1
3