Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

QBWIRE - Chip & Dale

Hai anh em Chip và Dale đang chơi trò chơi “nối dây”. Đó là trò chơi trên bảng có N × N nút lưới. Các nút của lưới được đánh số từ 0 đến N – 1 theo chiều từ trên xuống và 0 đến N – 1 theo chiều từ trái sang phải. Tọa độ của một nút được thể hiện bằng một cặp số trong đó số thứ nhất là tọa độ cột, số thứ hai là tọa độ dòng. Chip sẽ chọn ra 4 điểm A1, A2, B1, B2. Chip yêu cầu Dale sử dụng các nét vẽ ngang (dọc) theo các đường kẻ của lưới để vẽ 2 đường gấp khúc thỏa mãn:

- Đường gấp khúc thứ nhất nối A1 với A2.

- Đường gấp khúc thứ hai nối B1 với B2.

- Hai đường gấp khúc không có điểm chung.

- Tổng độ dài hai đường gấp khúc là nhỏ nhất có thể.

Dale có vẻ không thành thạo lắm với trò chơi này, bạn hãy giúp Dale tính tổng độ dài nhỏ nhất của hai đường gấp khúc.

Input

Dòng đầu ghi số nguyên T là số test.

Tiếp theo là T test, mỗi test được ghi trên 3 dòng

Dòng thứ nhất ghi số N.

Dòng thứ hai ghi 4 số là tọa độ cột của 4 điểm A1, A2, B1, B2.

Dòng thứ ba ghi 4 số là tọa độ dòng của 4 điểm A1, A2, B1, B2.

Output

Mỗi test ghi đáp số trên một dòng.

Nếu không có cách nối dây thỏa mãn, ghi ra -1.

Nếu có cách nối dây thỏa mãn, ghi ra tổng độ dài 2 đường gấp khúc.

Example

Input:
1
7
2 5 4 4
1 4 5 0

Output:
15

Giới hạn:
1 ≤ T ≤ 5 
2 ≤ N ≤ 500 

Được gửi lên bởi:special_one
Ngày:2008-10-12
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.