Teemo có một cánh đồng nấm gồm N*N ô. Các dòng được đánh số từ 1 đến N từ trên xuống dưới, các cột được đánh số từ 1 đến N từ trái sang phải. Teemo rất thích ma trận hình xoắn ốc vì vậy anh ta đã đánh số các ô nấm của mình theo số thứ tự xoắn ốc bắt đầu từ ô \((1, 1)\) . Hình xoắn ốc đi từ ngoài vào trong theo chiều kim đồng hồ. Hình dưới là ví dụ với bảng \(N = 5.\)

Rồi mùa thu hoạch nấm đã tới, Teemo đang ở vị trí của ô số \(X\) và muốn chuyển đến ô của số \(Y\) bằng cách thực hiện một số bước di chuyển. Trong mỗi bước, Teemo chỉ có thể di chuyển từ ô số A đến ô số B nếu:

• Ô chứa số \(A\) và ô chứa số \(B\) có chung một cạnh.
• \(A\) và \(B\) nguyên tố cùng nhau.

Cho \(N, X, Y\) , Teemo muốn biết số bước di chuyển ít nhất để chuyển từ ô số X đến ô số Y. Các bạn hãy giúp anh ấy nhé.

Dữ liệu nhập:

• Dòng đầu tiên chứa số nguyên T là số lượng test. \((1 ≤ T ≤ 10)\)
• Trong T dòng tiếp theo, mỗi test trên một dòng là 03 số nguyên N, X và Y \((1 ≤ N ≤ 1000 , 1 ≤ X, Y ≤ 10^6) \).

Dữ liệu xuất:

• Với mỗi test, in ra số bước ít nhất để di chuyển từ ô số X đến ô số Y. Nếu không di chuyển được in ra -1

Ví dụ

Input:

1

5 3 18

Output:

3

Thực hiện 3 bước:

• Từ ô số 3 chuyển qua ô số 4 (3 và 4 nguyên tố cùng nhau)
• Từ ô số 4 chuyển qua ô số 19 (4 và 19 nguyên tố cùng nhau)
• Từ ô số 19 chuyển qua ô số 18 (19 và 18 nguyên tố cùng nhau)