Dividing Marbles

Debbie, Debby, Debra and Deborah play a game with marbles. Debbie brought $2^{d_1}$ marbles, Debby brought $2^{d_2}$ marbles, Debra brought $2^{d_3}$ marbles, and Deborah brought $2^{d_4}$ marbles. They gathered every marble into a single pile, so that pile holds $2^{d_1} + 2^{d_2} + 2^{d_3} + 2^{d_4}$ marbles.

The game runs in turns. Each turn has two steps.

• Choose one pile that holds more than one marble and divide it into two non-empty piles. If the chosen pile holds $m \ge 2$ marbles, the two new piles hold $m_1$ and $m_2$ marbles, where $m_1$ and $m_2$ are positive integers with $m_1 + m_2 = m$.
• If several piles hold the same number of marbles, keep one of them and discard every other pile of that size.

The game ends when one pile is left and that pile holds a single marble. The game is cooperative. The four players do not play against each other, they reach the same goal together. The goal is to end the game in as few turns as possible.

For each test case, find the smallest number of turns that ends the game.

The first line contains the number of test cases $T$ ($1 \le T \le 500$).

Each of the next $T$ lines describes one test case and contains four non-negative integers $d_1$, $d_2$, $d_3$, $d_4$ ($0 \le d_i \le 20$).

For each test case, print the smallest number of turns that ends the game, one per line.

Take the test case where $d_1, d_2, d_3, d_4$ are $0, 1, 2, 3$. At the start there is one pile of $2^0 + 2^1 + 2^2 + 2^3 = 15$ marbles. On the first turn, divide 15 into 10 and 5. On the second turn, divide 10 into 5 and 5, which makes three piles of 5 marbles, so two of them are discarded and one pile of 5 marbles is left. On the third turn, divide 5 into 1 and 4. On the fourth turn, divide 4 into 2 and 2, so one pile of 2 marbles is discarded and piles of 1 and 2 marbles are left. On the fifth turn, divide 2 into 1 and 1, so two piles of 1 marble are discarded and a single pile of 1 marble is left, which ends the game. No play ends it in fewer than five turns, so the answer is 5.