Bốn Ô Đồng Màu

Một ảnh gồm đúng $2\times 2$ ô. Mỗi ô có một màu, được ký hiệu bằng một chữ cái Latin thường.

Trong một thao tác, bạn chọn không quá hai ô đang có cùng màu, rồi đổi tất cả các ô đã chọn sang cùng một màu khác. Hãy tìm số thao tác ít nhất để cả bốn ô có cùng màu.

Input

• Dòng đầu chứa số nguyên $t$ - số bộ test.
• Mỗi bộ test gồm hai dòng; mỗi dòng là một xâu độ dài $2$ mô tả một hàng của ảnh.

Output

• Với mỗi bộ test, in một số nguyên trên một dòng: số thao tác ít nhất.

Constraints

• $1\le t\le 1000$.
• Mỗi ký tự là một chữ cái Latin thường từ $a$ đến $z$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $t\le 20$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

4
aa
aa
aa
ab
ab
ac
ab
cd

0
1
2
3