Giải bài trực tuyến

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 A₁, A₂, B₁, B₂. 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 A₁ với A₂.

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

- 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 A₁, A₂, B₁, B₂.

Dòng thứ ba ghi 4 số là tọa độ dòng của 4 điểm A₁, A₂, B₁, B₂.

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