1024+1024

Time Limit: 1 Second    Memory Limit: 131072 KB

1024 + 1024 is a recent computer game and currently is being played all over the world. In this game, there is a 4 × 4 grid which is empty at the beginning of the game. As soon as the game starts, a tile with number 2 appears somewhere in the grid. In each turn of the game, the player can perform one of the available moves which are: up, right,down and left. Each of these moves makes all the umbered tiles in the grid move in that direction and a new tile with number 2 will be appeared in one of the empty grid’s cells randomly. When tiles are moving, if two tiles with the same number t collide to each other,they will merge into one tile with new number of 2t,and 2t points will be added to the score of player. Here is an example of this game:

Unfortunately, this game is hacked and the scoreboard is off. Your task is to write a program to get all the numbers which are currently in the grid and compute player’s score.

Input

First line of the input contains an integer n which is number of test cases. For each test, there will be 4 lines containing 16 space separated integers which are tiles’ numbers in the grid (0 means notile). It is guaranteed that final score does not exceeds 2³¹.

Output

For each test, print a single line containing player’s score.

Sample Input

2
4 0 0 8
0 0 0 0
0 2 0 0
0 0 0 0
16 0 0 0
0 0 0 0
4 2 0 0
0 0 0 0

Sample Output

20
52

Submit