Cho mảng \(A\), \(B\) đều có \(N\) phần tử. Nhiệm vụ của bạn là tìm giá trị nhỏ nhất của biểu thức \(P = A_1*B_1 + A_2*B_2 + ..+ A_{N-1}*B_{N-1} + A_{N}*B_{N}\) bằng cách tráo đổi vị trí các phần tử của cả mảng \(A và B\). Chú ý, kết quả của bài toán có thể rất lớn, vì vậy bạn hãy đưa ra kết quả lấy modulo với \(10^9+7\).

Input

• Dòng đầu tiên đưa vào số lượng bộ test \(T\) (\(1 \leq T \leq 100\)).
• Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test gồm \(3\) dòng:
  • Dòng thứ nhất đưa vào nguyên \(N\) (\(1 \leq N \leq 10^5\));
  • Dòng tiếp theo đưa vào \(N\) số \(A_i\) (\(1 \leq i \leq N, 1 \leq A_i \leq 10^{18}\));
  • Dòng cuối cùng đưa vào \(N\) số \(B_i\) (\(1 \leq i \leq N, 1\leq B_i \leq 10^{18}\));
• Các số được viết cách nhau một vài khoảng trống.
• Tổng tất cả \(N\) của \(T\) bộ test không quá \(10^6\).

Output

• Đưa ra kết quả mỗi test theo từng dòng.

Example

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

45
57