Loli đang chơi Arknights. Trong màn chơi hiện tại, Loli cần phải tiêu diệt ~n~ con quái, con quái thứ ~i~ có ~h_i~ điểm HP.

Nhân vật duy nhất đang gánh còng lưng Loli có hai kỹ năng:

• Chọn hai con quái đang sống và tấn công đồng thời hai bọn chúng, khiến mỗi con quái bị trừ ~1~ điểm HP.
• Chọn một con quái rồi dùng nội tại để tiêu diệt nó ngay lập tức.

Hai kỹ năng có thể được thực hiện vô hạn lần, với thứ tự thực hiện bất kỳ. Trong một đơn vị thời gian, Loli có thể sử dụng một trong hai kỹ năng đó.

Khi con quái có điểm HP về ~0~, nó sẽ bị tiêu diệt.

Tuy nhiên, Loli sắp bị mẹ gank. Vì vậy, Loli muốn biết hắn có thể quét sạch quái trong thời gian nhanh nhất là bao lâu.

Input:

Bài này có nhiều test nhỏ trong một file test, các bạn chú ý.

Lấy từ tệp DANHQUAI.INP gồm:

• Dòng đầu tiên chứa một số nguyên dương ~T~ ~(1\le T\le 500)~ là số test nhỏ.
• Có ~T~ test nhỏ, mỗi test nhỏ có cấu trúc như sau:
  • Dòng đầu tiên chứa một số nguyên dương ~n~ ~(1 \le n \le 10^5)~ - là số lượng quái cần đánh.
  • Dòng tiếp theo chứa ~n~ số nguyên dương ~h_i~ ~(1 \le h_i \le 100)~ là điểm HP của con quái thứ ~i~.

Output:

Ghi ra tệp DANHQUAI.OUT gồm:

• ~T~ dòng, dòng thứ ~i~ chứa một số nguyên tương ứng với đáp án của test nhỏ thứ ~i~.

Sample Input 1

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

Sample Output 1

3
3
5

Giải thích

• Ở test đầu tiên, có nhiều cách để tiêu diệt toàn bộ quái trong ~3~ đơn vị thời gian. Một cách đánh là:
  • Dùng kỹ năng thứ nhất lên con quái thứ ~1~ và ~2~. Quái thứ ~1~ còn ~1~ HP, quái thứ ~2~ bị tiêu diệt. Mảng còn lại là ~[1,0,1,2]~.
  • Dùng kỹ năng thứ nhất lên con quái thứ ~3~ và ~4~. Quái thứ ~4~ còn ~1~ HP, quái thứ ~3~ bị tiêu diệt. Mảng còn lại là ~[1,0,0,1]~.
  • Dùng kỹ năng thứ nhất lên con quái thứ ~1~ và ~4~. Cả hai con quái đều bị tiêu diệt.
• Ở test thứ hai, một cách đánh là:
  • Dùng kỹ năng thứ nhất lên con quái thứ ~2~ và ~3~. Cả hai con quái đều còn ~1~ HP. Mảng còn lại là ~[4,1,1]~.
  • Dùng kỹ năng thứ nhất lên con quái thứ ~2~ và ~3~. Cả hai con quái đều bị tiêu diệt. Mảng còn lại là ~[4,0,0]~.
  • Dùng kỹ năng thứ hai lên con quái thứ ~1~. Quái thứ ~1~ bị tiêu diệt.