Lò Cò là một trò chơi dân gian, được cho là đã có từ thời La Mã cổ đại, rất thông dụng và có ảnh minh hoạ trên các giáo đường. Trò chơi này rèn luyện người mới chơi tập trung giữ thăng bằng, nâng cao sự khéo léo và tính toán. Cụ thể, trên sân được vẽ N hình chữ nhật, các hình chữ nhật được đánh số từ 1 đến N. Người chơi cần di chuyển từ hình 1 đến hình N với luật di chuyển như sau: nếu người chơi đang ở hình thứ i thì có thể di chuyển tới hình thứ j nếu hình i và hình j có phần diện tích giao nhau khác 0.

Yêu cầu: Tìm cách di chuyển qua từ hình 1 đến hình N mà qua ít hình chữ nhật nhất.

Dữ liệu:

• Dòng 1: chứa số N (N ≤ 1000) là số hình chữ nhật;

• N dòng sau, mỗi dòng chứa 4 số , trong đó (tx, ty) là tọa độ tâm của hình chữ nhật và (px, py) là tọa độ của một đỉnh của hình chữ nhật. (|tx|, |ty|, |px|, |py| <=1000000)

Kết quả:

Ghi số bước nhảy ít nhất để di chuyển từ hình 1 đến hình thứ N, nếu không di chuyển được thì ghi -1.

Sample Input

3
0 0 1 1
1 0 2 1
4 0 7 2

Sample Output

2

Sample Input

3
0 0 1 1
2 0 3 1
4 0 5 1

Sample Output

-1