Untitled

2048

Game 2048 is set up on a board 4x4, include random number 0 and M with M = 2^n (0<=n<=11).

You can arrange the array in horizontal or vertical directions. In each arrangement, all rows or columns will be stacked in the corresponding direction. During arrangement, two adjacent numbers with the same value will be added up to make a number.

For examples:
 

After K times of moving (2<=K<=11), find and print on the screen the largest number in the array which you create.

Input


1 //The number of test case

3 //K: The number of moves (arrangement)

0 2 2 0
4 0 0 0

0 0 8 0
2 2 4 0

 

Output:

#1 16

Input:
50
3
0 2 2 0
4 0 0 0
0 0 8 0
2 2 4 0
2
0 2 2 0
4 0 0 0
0 0 8 0
2 2 4 0
4
0 2 2 0
4 0 0 0
0 0 8 0
2 2 4 8
3
2 2 2 2
4 4 4 4
8 8 8 8
16 16 16 16
4
2 0 0 0
0 4 0 0
0 8 0 0
0 0 0 2
7
2 0 0 0
0 4 0 0
0 8 0 0
0 0 0 2
6
0 4 2 0
4 0 0 0
0 0 8 2
2 2 4 8
4
8 2 2 2
4 2 4 8
16 8 2 2
2 4 8 4
9
8 2 2 2
4 2 4 8
16 8 2 2
2 4 8 4
11
8 4 16 2
4 8 4 8
16 8 2 2
2 4 8 4
9
4 0 32 64 
4 64 0 4 
8 4 16 4 
32 2 0 0 
8
8 0 2 16 
0 64 16 2 
32 16 4 2 
2 0 4 2 
9
2 4 2 4 
2 64 32 8 
32 2 64 16 
8 4 32 0 
10
4 8 2 32 
32 32 2 32 
0 0 32 4 
4 16 4 64 
10
32 16 16 0 
0 32 0 8 
64 2 64 4 
2 16 4 64 
10
8 64 32 16 
8 8 4 32 
2 2 8 16 
0 64 16 64 
10
64 8 8 8 
8 2 32 64 
2 64 16 2 
8 32 32 16 
9
16 0 2 2 
32 16 16 8 
4 32 2 8 
16 0 0 0 
11
64 0 0 32 
32 32 64 4 
4 32 16 8 
0 8 4 64 
11
8 4 16 32 
8 2 4 2 
0 8 2 0 
0 64 4 4 
8
64 32 4 32 
0 4 16 2 
8 32 0 8 
16 32 2 0 
8
16 4 64 2 
16 8 0 16 
32 8 4 64 
0 0 0 4 
9
4 8 8 64 
32 64 0 4 
2 8 0 0 
4 16 8 2 
8
16 0 16 8 
2 8 16 8 
64 32 0 2 
32 8 16 16 
10
8 0 4 64 
0 2 2 64 
4 0 0 8 
16 2 0 16 
9
64 64 8 32 
64 32 16 64 
4 32 4 16 
16 8 4 0 
10
8 2 4 64 
16 64 8 2 
0 0 16 16 
64 8 4 16 
10
16 16 8 8 
0 0 2 8 
2 0 0 32 
0 8 32 8 
8
4 4 4 4 
16 0 64 16 
0 0 8 0 
32 16 0 2 
11
8 0 2 16 
64 2 2 2 
8 32 0 4 
8 2 0 4 
9
4 4 2 64 
4 16 32 64 
4 32 0 0 
64 2 16 32 
10
16 4 2 2 
16 4 2 8 
64 16 16 0 
16 32 2 0 
8
0 32 2 0 
0 0 16 8 
4 4 0 2 
64 2 16 0 
8
32 64 2 64 
4 16 16 8 
2 2 8 2 
0 16 64 32 
8
64 64 64 2 
32 64 8 4 
64 8 16 2 
8 8 64 4 
9
64 32 0 64 
16 0 32 0 
8 16 4 8 
0 4 32 2 
11
32 64 32 16 
64 2 32 4 
8 16 32 32 
4 4 16 64 
11
8 16 2 16 
8 8 0 0 
64 16 32 2 
8 16 0 32 
10
32 0 16 2 
4 8 8 32 
32 64 16 16 
16 8 2 2 
8
0 16 2 0 
64 0 8 4 
4 0 8 8 
8 64 32 4 
11
4 64 4 64 
2 0 2 16 
8 64 4 32 
4 4 8 64 
8
2 16 8 8 
0 8 8 4 
64 4 16 16 
32 8 8 64 
9
8 16 64 64 
32 2 64 8 
32 4 0 2 
16 4 4 2 
11
8 2 64 32 
4 16 0 32 
4 4 4 2 
8 0 4 2 
8
2 2 64 32 
0 16 16 2 
8 32 32 2 
16 32 4 16 
8
32 0 0 8 
2 4 0 4 
4 2 16 0 
0 0 8 64 
10
64 8 8 2 
16 16 32 2 
2 4 8 4 
64 16 4 64 
10
2 4 0 0 
2 16 8 32 
8 2 4 32 
64 8 2 8 
11
8 2 2 0 
0 8 8 64 
2 2 32 16 
8 8 4 32 
8
32 32 64 32 
32 32 64 32 
32 64 32 64 
64 64 32 64 

Output:
#1 16
#2 8
#3 16
#4 64
#5 8
#6 16
#7 32
#8 32
#9 64
#10 64
#11 128
#12 128
#13 128
#14 128
#15 256
#16 256
#17 256
#18 128
#19 256
#20 128
#21 128
#22 128
#23 128
#24 128
#25 128
#26 256
#27 256
#28 128
#29 128
#30 128
#31 256
#32 128
#33 128
#34 256
#35 256
#36 256
#37 256
#38 128
#39 128
#40 128
#41 256
#42 128
#43 256
#44 128
#45 128
#46 128
#47 256
#48 128
#49 128
#50 512
Editor is loading...