CF1792A GamingForces

Monocarp is playing a computer game. He's going to kill $ n $ monsters, the $ i $ -th of them has $ h_i $ health. Monocarp's character has two spells, either of which he can cast an arbitrary number of times (possibly, zero) and in an arbitrary order: - choose exactly two alive monsters and decrease their health by $ 1 $ ; - choose a single monster and kill it. When a monster's health becomes $ 0 $ , it dies. What's the minimum number of spell casts Monocarp should perform in order to kill all monsters?

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases. The first line of each testcase contains a single integer $ n $ ( $ 1 \le n \le 100 $ ) — the number of monsters. The second line contains $ n $ integers $ h_1, h_2, \dots, h_n $ ( $ 1 \le h_i \le 100 $ ) — the health of each monster. The sum of $ n $ over all testcases doesn't exceed $ 2 \cdot 10^4 $ .

For each testcase, print a single integer — the minimum number of spell casts Monocarp should perform in order to kill all monsters.

In the first testcase, the initial health list is $ [1, 2, 1, 2] $ . Three spells are casted: - the first spell on monsters $ 1 $ and $ 2 $ — monster $ 1 $ dies, monster $ 2 $ has now health $ 1 $ , new health list is $ [0, 1, 1, 2] $ ; - the first spell on monsters $ 3 $ and $ 4 $ — monster $ 3 $ dies, monster $ 4 $ has now health $ 1 $ , new health list is $ [0, 1, 0, 1] $ ; - the first spell on monsters $ 2 $ and $ 4 $ — both monsters $ 2 $ and $ 4 $ die. In the second testcase, the initial health list is $ [2, 4, 2] $ . Three spells are casted: - the first spell on monsters $ 1 $ and $ 3 $ — both monsters have health $ 1 $ now, new health list is $ [1, 4, 1] $ ; - the second spell on monster $ 2 $ — monster $ 2 $ dies, new health list is $ [1, 0, 1] $ ; - the first spell on monsters $ 1 $ and $ 3 $ — both monsters $ 1 $ and $ 3 $ die. In the third testcase, the initial health list is $ [1, 2, 3, 4, 5] $ . Five spells are casted. The $ i $ -th of them kills the $ i $ -th monster with the second spell. Health list sequence: $ [1, 2, 3, 4, 5] $ $ \rightarrow $ $ [0, 2, 3, 4, 5] $ $ \rightarrow $ $ [0, 0, 3, 4, 5] $ $ \rightarrow $ $ [0, 0, 0, 4, 5] $ $ \rightarrow $ $ [0, 0, 0, 0, 5] $ $ \rightarrow $ $ [0, 0, 0, 0, 0] $ .