Có N ô tô (đánh số từ 1 tới N) trên đường tròn có độ dài N. Với mỗi i (2 ≤ i ≤ N), chiếc ô tô thứ i có khoảng cách i – 1 theo chiều kim đồng hồ so với ô tô 1. Tức là ô tô 1 cần đi đoạn đường dài i – 1 theo chiều kim đồng hồ để tới được chỗ ô tô i.

Với mỗi i, bạn có thể đổ xăng vào ô tô thứ i lên tới ~f_i~ lít, với chi phí là ~c_i~ đồng mỗi lít. Sau đó, bạn chọn một ô tô, ngồi lên đó và bắt đầu lái theo chiều kim đồng hồ. Để di chuyển một đơn vị khoảng cách theo chiều này, bạn cần 1 lít xăng. Khi bạn đi qua một chiếc ô tô khác (kể cả khi bạn hết xăng ở điểm đó). Một khi bạn không còn xăng nữa, bạn sẽ dừng lại.

Nhiệm vụ của bạn là đổ xăng sao cho bạn có thể chọn một xe tối ưu, đi một vòng theo chiều kim đồng hồ với độ dài N và quay lại vị trí ban đầu. Dưới sự ràng buộc này, bạn muốn trả ít tiền nhất có thể.

Tìm chi phí nhỏ nhất bạn cần trả. Dữ liệu đảm bảo rằng có cách để đi được khoảng cách N. Có thể chứng minh rằng số tiền nhỏ nhất luôn là số nguyên.

Dữ liệu vào

• Dòng đầu tiên của dữ liệu vào chứa một số nguyên T thể hiện số test. T test được mô tả như sau:
• Dòng đầu tiên của mỗi test chứa một số nguyên N
• Dòng thứ hai chứa N số nguyên ~f_1, f_2, …, f_N~
• Dòng thứ hai chứa N số nguyên ~c_1, c_2, …, c_N~

Dữ liệu ra

• Với mỗi test, in ra một dòng chứa một số nguyên – chi phí nhỏ nhất bạn cần trả.

Ràng buộc

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 200000
• 0 ≤ ~f_i~ ≤ ~10^9~ với mọi i
• 0 ≤ ~c_i~ ≤ ~10^9~ với mọi i

Ví dụ

Input

3 
3 
1 1 1 
1 1 1 
3 
3 0 0 
10 0 0 
3 
3 3 3 
3 2 1

Output

3 
30 
3