Khi rảnh rỗi, Bessie thích nghiên cứu vật lý thực nghiệm. Gần đây cô đã phát hiện ra một cặp hạt hạ nguyên tử mới, được đặt tên là mootrinos và antimootrinos. Giống như các cặp vật chất-phản vật chất tiêu chuẩn, mootrinos và antimootrino tiêu hủy lẫn nhau và biến mất khi chúng gặp nhau. Nhưng điều làm cho những hạt này trở nên độc đáo là chúng thay đổi hướng chuyển động (trong khi vẫn giữ nguyên tốc độ) bất cứ khi nào Bessie nhìn vào chúng.
Đối với thí nghiệm mới nhất của mình, Bessie đã xếp một lượng chẵn \(N(2 \le N \le 10^5)\) các hạt này vào một dòng. Dòng bắt đầu bằng mootrino ở bên trái và sau đó xen kẽ giữa hai loại hạt, với hạt thứ i nằm ở vị trí \(p_i(0 \le p_1 < ... < p_n \le 10^18)\). Mootrinos di chuyển sang phải trong khi antimootrinos di chuyển sang trái, và hạt thứ \(i\) chuyển động với tốc độ không đổi là \(s_i\) đơn vị mỗi giây \((1 \le s_i \le 10^9)\).
Bessie quan sát vào các thời điểm sau:

• Đầu tiên, \(1\) giây sau khi bắt đầu thí nghiệm.
• Sau đó \(2\) giây sau lần quan sát đầu tiên.
• Sau đó \(3\) giây sau lần quan sát thứ hai.
• ...
• Sau đó \(n+1\) giây sau lần quan sát thứ \(n\).
  Trong mỗi lần quan sát, Bessie ghi lại những hạt nào đã biến mất.
  Thí nghiệm này có thể mất rất nhiều thời gian để hoàn thành, vì vậy Bessie trước tiên muốn mô phỏng kết quả của nó. Với cách thiết lập thí nghiệm, hãy giúp Bessie xác định khi nào (tức là số lần) cô ấy sẽ quan sát thấy từng hạt biến mất! Nó có thể được chứng minh rằng tất cả các hạt cuối cùng sẽ biến mất.

Input

• Mỗi bộ test chứa \(T (1\le T \le 10)\) test độc lập.
• Mỗi trường hợp thử nghiệm bao gồm ba dòng. Dòng đầu tiên chứa \(N\), dòng thứ hai chứa \(p_1,p_2,...,p_N\), và dòng thứ ba chứa \(s_1,s_2,...,s_N\).
• Tổng N không vượt quá \(2*10^5\)

Output

Đối với mỗi test, in ra số lần quan sát cho sự biến mất của từng hạt, cách nhau bằng dấu cách.

Scoring

• Subtask \(1\): \(N=2\)
• Subtask \(2\): \(N \le 2000\) và \(p_i \le 10^4\)
• Subtask \(3\): \(N \le 2000\)
• Subtask \(4\): Không có điều kiện gì thêm.

Example

4
2
1 11
1 1
2
1 12
1 1
2
1 11
4 6
2
1 11
4 5

9 9
11 11
1 1
3 3

2
4
1 3 5 8
1 1 1 1
4
1 4 5 8
1 1 1 1

1 1 3 3
7 2 2 7