Teemo Hái Nấm


Submit solution

Points: 4 (partial)
Time limit: 0.8s
Memory limit: 98M

Author:
Problem type

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.\)

enter image description here

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 \le T \le 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 \le N \le 1000 , 1 \le X, Y \le 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)

Comments


  • 0
    ndh96coder  commented on Feb. 11, 2018, 11:54 a.m.

    XIn lỗi các bạn. Cập nhật lại N <= 1000 nhé