Có 16 đồng xu xếp thành bảng 4×4, mỗi đồng xu có thể úp hoặc ngửa như hình vẽ:

Tại mỗi bước ta có phép biến đổi sau: Chọn một đồng xu và thay đổi trạng thái của đồng xu đó và tất cả các đồng xu tiếp xúc với nó (úp thành ngửa, ngửa thành úp).

Yêu cầu:

Cho trước một trạng thái các đồng xu, hãy lập trình tìm số phép biến đổi ít nhất để đưa về trạng thái tất cả các đồng xu hoặc đều úp hoặc đều ngửa.

Dữ liệu:

• Dòng 1 ghi số ~C≤10^4~ là số test.
  
• Tiếp theo là ~C~ nhóm dòng, mỗi nhóm gồm 4 dòng, mỗi dòng gồm 4 kí tự miêu tả trạng thái của mỗi đồng xu. Kí tự ~H~ thể hiện đồng xu đang ngửa, kí tự ~T~ thể hiện đồng xu úp.

Kết quả:

Với mỗi test, ghi ra trên một dòng số phép biến đổi ít nhất để đưa 16 đồng xu về tất cả trạng thái đều úp hoặc đều ngửa. Nếu không thể thực hiện được, in ra "Impossible".

Input

2
HTTH
THTT
HHHT
HHTH
HTHT
THTH
HTHT
THTH

Output

3
Impossible