Một bàn cờ vua có kích thước \(8 \times 8\).

• Các cột được đánh số từ a đến h.
• Các hàng được đánh số từ 1 đến 8.

Một quân mã có thể di chuyển theo quy tắc sau:

Bạn cần trả lời \(Q\) truy vấn: Hiện tại quân mã đang ở ô \(x\), hãy đếm số bước đi ít nhất để quân mã đến ô \(y\).

Input

• Dòng thứ nhất gồm số nguyên dương \(Q\) (\(Q \leq 4000\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai xâu \(x\) và \(y\).
  Mỗi xâu gồm hai ký tự: ký tự đầu là cột, ký tự thứ hai là hàng.

Output

• In ra số lần quân mã cần di chuyển ít nhất cho mỗi truy vấn trên các dòng khác nhau.

Example

3
a1 h8
h8 c3
a1 c2

6
4
1