3의 열차

Threes!는 iOS와 Android 등에서 즐길 수 있는 퍼즐 게임이다. 규칙은 단순하지만 그 안의 구조는 깊다. 이웃한 수를 맞춰 합치는 일을 반복해서 더 큰 수를 만들어 나간다. 여기서는 이 게임을 단순하게 바꾼 버전을 다룬다.

게임은 수 $N$개로 이루어진 배열에서 시작한다. 각 수는 $1$이거나 $2$이거나, $i \ge 0$인 정수 $i$에 대해 $3 \times 2^i$ 꼴이다.

이웃한 두 수가 서로 맞으면 하나로 합쳐서 더 큰 수를 만들 수 있다. 이웃한 $1$과 $2$는 합쳐서 $3$ 하나가 된다. 이웃한 $3$ 두 개는 $6$ 하나가 되고, 이웃한 $6$ 두 개는 $12$ 하나가 되며, 일반적으로 $3$ 이상인 같은 수 두 개가 이웃해 있으면 두 수의 합 하나로 합칠 수 있다. $1$과 $2$는 특별하다. $1$은 $2$하고만 맞고, $2$는 $1$하고만 맞는다.

게임의 목표는 만들 수 있는 가장 큰 수를 만드는 것이다. 이웃한 두 수를 더 이상 합칠 수 없게 되면 게임이 끝난다. 예를 들어 배열 $\{12, 24, 6, 1, 2, 3, 12, 3, 3, 6, 1, 2, 2, 1, 24\}$에서 시작하면 만들 수 있는 가장 큰 수는 $48$이다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다 ($1 \le T \le 1000$). 이어서 $2T$개의 줄이 주어진다. 각 테스트 케이스의 첫 줄에는 배열의 크기 $N$이 주어진다 ($1 \le N \le 10000$). 그다음 줄에는 정수 $N$개가 주어지며, 각 정수는 $1$, $2$, 또는 $0 \le i \le 11$인 정수 $i$에 대해 $3 \times 2^i$ 꼴이다.

테스트 케이스 $T$개 각각에 대해 만들 수 있는 가장 큰 수를 한 줄에 출력한다.