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.
  • AB 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é