Harmonizing Grid Cell Frequencies

Bạn có một bảng điều khiển kích thước $2 × 2$ gồm $4$ ô vi mạch. Mỗi ô vi mạch mang một ký tự đại diện cho một trong $26$ mức tần số khác nhau, được ký hiệu bằng các chữ cái tiếng Anh viết thường.

Bạn muốn điều chỉnh tần số của các ô vi mạch sao cho cả $4$ ô đều có cùng một mức tần số. Trong mỗi thao tác, bạn có thể chọn tối đa hai ô vi mạch đang có cùng mức tần số và đổi tần số của chúng sang một mức tần số mới. Lưu ý rằng nếu bạn chọn hai ô vi mạch, cả hai ô đó đều phải được chuyển sang cùng một mức tần số mới.

Hãy xác định số thao tác tối thiểu cần thực hiện để đạt được mục tiêu.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $t$ ($1 ≤ t ≤ 1000$) là số lượng bộ dữ liệu.

Mỗi bộ dữ liệu gồm hai dòng. Mỗi dòng chứa hai chữ cái tiếng Anh viết thường không có ký tự phân cách, biểu diễn các mức tần số của một hàng ô vi mạch trên bảng điều khiển.

Kết quả

Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất là số thao tác tối thiểu cần thực hiện để tất cả $4$ ô vi mạch trên bảng điều khiển đều có cùng mức tần số.

Chấm điểm

Subtask 1 (30 points). $t ≤ 20$

Subtask 2 (70 points). $1 ≤ t ≤ 1000$

Ví dụ

Input

5
rb
br
cc
wb
aa
aa
ab
cd
yy
xx

Output

1
2
0
3
1

Ghi chú

Phân tích các bộ dữ liệu trong ví dụ:

Ở bộ dữ liệu thứ nhất, bạn có thể điều chỉnh ô ở góc dưới bên trái và ô ở góc trên bên phải (hai ô này đang có cùng mức tần số) sang mức tần số r, khi đó tất cả các ô đều có cùng mức tần số này.

Ở bộ dữ liệu thứ hai, hai thao tác là đủ:

• Điều chỉnh cả hai ô ở hàng trên (đang có cùng mức tần số c) sang mức tần số b.
• Điều chỉnh ô ở góc dưới bên trái sang mức tần số b.

Ở bộ dữ liệu thứ ba, tất cả các ô đã có sẵn cùng một mức tần số.

Ở bộ dữ liệu thứ tư, bạn có thể giữ nguyên mức tần số của một ô bất kỳ và điều chỉnh ba ô còn lại sang mức tần số của ô đó trong ba thao tác.

Ở bộ dữ liệu thứ năm, bạn có thể điều chỉnh cả hai ô ở hàng trên sang mức tần số x.