Cho một quân mã trên bàn cờ vua tai vị trí ST. Nhiệm vụ của bạn là hãy tìm số bước di chuyển ít nhất để đưa quân mã tới vị trí EN.

Định dạng đầu vào: Dòng đầu tiên là số lượng bộ test T (T ≤ 20). Mỗi test gồm 2 xâu dạng "xy" và "uv", trong đó x, y là kí tự trong "abcdefgh" còn y, v là số thuộc 1, 2, 3, 4, 5, 6, 7, 8.

Ràng buộc: N/A

Định dạng đầu ra: Với mỗi test, in ra đáp án tìm được trên một dòng. Nếu không thể tìm được đường in ra -1.

Input:

5
b2 c6
h4 b3
g1 b2
e2 c3
f6 b2

Output:

3
3
4
1
4