Sau khi đánh bại tên Pháp sư vực sâu và bè lũ Hilichurl, bạn đã có thể đối diện với boss cuối của cửa ải, đó chính là Phong ma long trong truyền thuyết. Để chuẩn bị cho cuộc chạm trán này, bạn đã chuẩn bị cho mình một vũ khí bí mật, đó là các tinh thể nguyên tố. Những tinh thể này đã được tinh luyện hàng trăm năm và chứa trong mình sức mạnh vô song, thứ sức mạnh hiếm hoi có thể sánh ngang hàng với sức mạnh của Phong ma long. Các tinh thể nguyên tố được đánh số từ ~1~ tới ~N~ và tinh thể thứ ~i~ sẽ có chỉ số sức mạnh là ~a_i~. Tuy nhiên, các tinh thể nguyên tố này lại liên quan mật thiết với nhau và không thể muốn dùng tinh thể nào trước cũng được. Bạn chỉ được sử dụng một tinh thể một lần, sau khi sử dụng thì tinh thể sẽ lập tức tan biến và bạn chỉ có thể sử dụng tinh thể có số thứ tự lớn nhất hoặc bé nhất chưa sử dụng (Các số thứ tự sẽ luôn được giữ nguyên). Ngoài ra, mỗi tinh thể có thể sử dụng theo một trong hai cách sau:

• Tăng Điểm bạo kích của bạn lên thêm ~1~
• Gây ra sát thương lên Phong ma long một lượng bằng Điểm bạo kích nhân với chỉ số sức mạnh của tinh thể. Sau khi gây sát thương, Điểm bạo kích sẽ quay trở lại giá trị ~1~

Ban đầu, Điểm bạo kích của bạn là ~1~. Hãy tìm cách sử dụng các tinh thể một cách tối ưu để gây ra lượng sát thương tối đa lên Phong ma long.

Input

• Dòng đầu tiên là một số nguyên dương ~T (T \leq 200)~ là số lượng bộ test.
• Dòng đầu tiên của mỗi bộ test là số nguyên dương ~N~.
• Dòng thứ hai của mỗi bộ test gồm ~N~ số nguyên dương ~a_i \leq 10^9 (1 \leq i \leq N)~ là chỉ số sức mạnh của các tinh thể nguyên tố.

Output

• Gồm ~T~ dòng, mỗi dòng in ra một số duy nhất là lượng sát thương tối đa có thể gây ra lên Phong ma long.

Sample input

2
2
1 2
3
1 1 1

Sample output

4
3

Giải thích

• Ở ví dụ đầu tiên, ta có thể sử dụng tinh thể thứ nhất để tăng Điểm bạo kích lên ~2~, sau đó dùng tinh thể thứ hai để gây sát thương là ~2 * 2 = 4~
• Ở ví dụ thứ hai, ta có thể lần lượt sử dụng các tinh thể có số thứ tự từ ~1~ tới ~3~ để gây sát thương.

Tính điểm

• Subtask 1: 50% số test có ~N \leq 10^2~ và tổng số ~N~ trong các bộ test không vượt quá ~10^3~
• Subtask 2: 50% số test có ~N \leq 10^5~ và tổng số ~N~ trong các bộ test không vượt quá ~10^6~