Mô tả

Lò Cò (hay cò 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 họa 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 chữ nhật j có phần diện tích giao nhau khác 0.

Yêu cầu

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

Dữ liệu vào

• 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ố nguyên tx, ty, px, py (|tx|, |ty|, |px|, |py| ≤ 10^6), trong đó: (tx, ty) là tọa độ tâm của hình chữ nhật,(px, py) là tọa độ một đỉnh của hình chữ nhật.

Dữ liệu ra

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

Input

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

Output

2

Input

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

Output

-1