Trên mặt phẳng tọa độ vô hạn, người ta xây nhà tại tất cả các tọa độ \((x, y)\) khi và chỉ khi \(x\) và \(y\) đồng thời là số nguyên tố.

Để cung cấp điện cho những ngôi nhà này, chính phủ có \(Q\) dự án đặt trạm phát điện.

Ở dự án thứ \(i\), chính phủ dự kiến xây trạm phát điện tại tọa độ \((X_i, Y_i)\). Trạm phát điện này sẽ cung cấp điện cho tất cả những ngôi nhà nằm trong khu vực hình chữ nhật có hai đỉnh đối nhau là \((u_i, v_i)\) và \((p_i, q_i)\).

Chi phí để truyền tải điện từ trạm điện đặt tại tọa độ \((a, b)\) đến ngôi nhà đặt tại tọa độ \((c, d)\) chính là khoảng cách Manhattan giữa chúng, được tính bằng công thức:

Với mỗi dự án, hãy cho biết tổng chi phí truyền tải điện của dự án đó.

Lưu ý rằng các dự án đều là giả định và độc lập với nhau.

Input

• Dòng đầu tiên chứa số nguyên dương \(Q\).
• \(Q\) dòng tiếp theo, dòng thứ \(i\) chứa sáu số nguyên dương \(X_i, Y_i, u_i, v_i, p_i, q_i\).

Output

• In ra \(Q\) dòng, dòng thứ \(i\) chứa một số nguyên không âm là kết quả của dự án thứ \(i\).

Constraints

• Trong mọi test, \(1 \le Q \le 10^5\).
• Với mỗi dự án, \(1 \le u_i \le X_i \le p_i \le 10^6\) và \(1 \le v_i \le Y_i \le q_i \le 10^6\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(X_i, Y_i, u_i, v_i, p_i, q_i \le 100\) với mọi \(i\); \(Q \le 10^4\).
• Subtask \(2\) (\(25\%\) số điểm): \(u_i = p_i = 2\) và \((X_i, Y_i) = (p_i, q_i)\) với mọi \(i\).
• Subtask \(3\) (\(25\%\) số điểm): \((X_i, Y_i) = (p_i, q_i)\) với mọi \(i\).
• Subtask \(4\) (\(25\%\) số điểm): Không có giới hạn gì thêm.

Example

3
2 2 1 1 4 4
1 1 1 1 1 5
3 6 1 3 5 7

4
0
24