Gita has been recently introduced to 2048 game. He is finding it pretty exciting. But being a noob in the game, he is baffled by the scoring of the game.

The formal definition of a standard 2048 game can be found here - http://en.wikipedia.org/wiki/2048_%28video_game%29

He asks you to find out the maximum score of the game by showing you the current board configuration. Can you help him find out the current maximum score possible for the given board configuration?

Please note that, in a 2048 game, if 2 tiles merge, than value on the final tile is added to the score of the game.

Input

First line contains T the no. of test cases. Each test case contains 4 lines. Each of these lines contains exactly 4 integers. Empty tiles are denoted by a 0.

Output

Output exactly 1 integer per test case, the maximum score possible for the given 2048 board configuration.

Example

Input:
2
4 8 2 0
0 0 0 0
0 0 0 0
2 0 0 0
16 4 0 0
0 0 0 2
0 0 0 0
0 0 0 0
 Output: 
20
52