Train of Threes

Threes! is a puzzle game available on iOS, Android, and other platforms. The rules are simple, but the structure behind them is deep: you repeatedly match adjacent numbers to build larger numbers. Here you play a simplified version of the game.

The game starts with an array of $N$ numbers. Each number is $1$, or $2$, or of the form $3 \times 2^i$ for some integer $i \ge 0$.

You can combine two matching adjacent numbers into a larger number. A $1$ next to a $2$ combines into a single $3$. Two adjacent $3$s combine into a single $6$, two adjacent $6$s combine into a single $12$, and in general two identical adjacent numbers that are at least $3$ combine into a single number equal to their sum. The numbers $1$ and $2$ are special: a $1$ matches only a $2$, and a $2$ matches only a $1$.

The goal of the game is to form the largest number possible. The game ends when no two adjacent numbers can be combined. For example, starting from the array $\{12, 24, 6, 1, 2, 3, 12, 3, 3, 6, 1, 2, 2, 1, 24\}$, the largest number you can form is $48$.

The first line contains an integer $T$, the number of test cases ($1 \le T \le 1000$). Then follow $2T$ lines. The first line of each test case contains an integer $N$, the size of the array ($1 \le N \le 10000$). The next line contains $N$ integers, where each integer is $1$, $2$, or of the form $3 \times 2^i$ for some integer $0 \le i \le 11$.

For each of the $T$ test cases, print the largest number that can be formed on its own line.