구슬 나누기

Debbie, Debby, Debra, Deborah가 구슬 놀이를 한다. Debbie는 구슬 $2^{d_1}$개, Debby는 $2^{d_2}$개, Debra는 $2^{d_3}$개, Deborah는 $2^{d_4}$개를 가져왔다. 네 사람은 가져온 구슬을 모두 한 무더기로 모았고, 이 무더기에는 구슬 $2^{d_1} + 2^{d_2} + 2^{d_3} + 2^{d_4}$개가 있다.

놀이는 차례를 거듭하며 진행한다. 한 차례는 다음 두 단계로 이루어진다.

• 구슬이 두 개 이상 있는 무더기 하나를 골라 비어 있지 않은 두 무더기로 나눈다. 고른 무더기의 구슬이 $m \ge 2$개이면 새로 생기는 두 무더기의 구슬 개수 $m_1$, $m_2$는 양의 정수이고 $m_1 + m_2 = m$을 만족한다.
• 구슬 개수가 같은 무더기가 여럿 있으면 그중 하나만 남기고 같은 개수의 나머지 무더기는 모두 버린다.

무더기가 하나만 남고 그 무더기에 구슬이 한 개만 있으면 놀이가 끝난다. 이 놀이는 협동 놀이다. 네 사람은 서로 겨루지 않고 함께 같은 목표를 이룬다. 목표는 놀이를 가장 적은 차례에 끝내는 것이다.

각 테스트 케이스마다 놀이를 끝내는 데 필요한 차례 수의 최솟값을 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 500$)

다음 $T$개의 줄에 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄에는 음이 아닌 정수 $d_1$, $d_2$, $d_3$, $d_4$가 주어진다. ($0 \le d_i \le 20$)

각 테스트 케이스마다 놀이를 끝내는 데 필요한 차례 수의 최솟값을 한 줄에 하나씩 출력한다.

$d_1, d_2, d_3, d_4$가 각각 $0, 1, 2, 3$인 경우를 보자. 처음에는 구슬 $2^0 + 2^1 + 2^2 + 2^3 = 15$개짜리 무더기 하나가 있다. 첫 차례에 15개를 10개와 5개로 나눈다. 둘째 차례에 10개를 5개와 5개로 나누면 5개짜리 무더기가 셋이 되므로 둘을 버리고 5개짜리 무더기 하나만 남는다. 셋째 차례에 5개를 1개와 4개로 나눈다. 넷째 차례에 4개를 2개와 2개로 나누면 2개짜리 무더기 하나를 버려 1개짜리와 2개짜리 무더기가 남는다. 다섯째 차례에 2개를 1개와 1개로 나누면 1개짜리 무더기 둘을 버리고 하나만 남아 놀이가 끝난다. 다섯 차례보다 적게는 끝낼 수 없으므로 답은 5이다.