import java.util.Scanner;
import java.io.*;

/*
 * Lab 9
 *
 * Author: Robin Dawes
 *
 * Date: 20091126
 *
 * Comment: 
 *
 */

public class Brains {

    static int instances;
    static int numOfDays;
    static int[] zombies;
    
    static int[][] table;
 
    public static void main (String[] argv) throws Exception {
        Scanner myScanner = new Scanner(new File("Lab_9_Data.txt"));
        // find out how many instances
        instances = myScanner.nextInt();
        for (int i = 0; i < instances; i++) {
            System.out.println("\nInstance " + i + " input: ");
            numOfDays = myScanner.nextInt();
            zombies = new int[numOfDays];
            
            for (int d = 0; d < numOfDays; d++){
                    zombies[d] = myScanner.nextInt();
                    System.out.format("%11d\t",zombies[d]);                    
            }
            System.out.println();
            
            
            
            
            table = new int[numOfDays+1][numOfDays];
            
             /*
             * table[i][j] is the maximum number of zombies we can zap on day j if the ZombieZapper has been charging for i days
             * The final column of the table corresponds to the last day of the attack.  We know we should always fire the ZZ on
             * the last day.
            
             * Note that the 0th row of the table is not used since we can't fire the ZZ twice on the same day.
            
             * The recurrence relation is
            
             *  Z(n-1,j) = min{A(n-1),32,2^j} for all values of j (in [0..n-1])
            
             *  Z(d,j) = max {
             *                 min{A(d),32,2^(j-1)} + Z(d+1,1),
             *                 Z(d+1,j+1)
             *               }                              for all values of j in [0..n-1], and all d < n-1
            
            
             * In the recurrence relation, the number of days of charging is the second dimension of the table.  When I coded this 
             * I reversed the dimensions of the table.
            
             */
            
            
            // fill in the last column of the table
            
            for (int r = 1; r <= numOfDays; r++) {
                table[r][numOfDays-1] = Math.min(32,
                                                  Math.min(zombies[numOfDays-1],
                                                           (int) Math.pow(2,r-1)
                                                          )
                                                  );     
            }
            

            // fill in the rest of the table
            
            for (int c = numOfDays-2; c >= 0; c--) {
                for (int r = 1; r <= c+1; r++) {
                        // since the ZZ starts uncharged, the maximum number of days of charging on day c is c+1
                        
                        table[r][c] = Math.max(Math.min(32,
                                                          Math.min(zombies[c],
                                                                   (int) Math.pow(2,r-1)
                                                                  )
                                                        ) + table[1][c+1],
                                                table[r+1][c+1]                    
                                               );
                }
            }
                
            
            System.out.println("The table:");
            
            
            for (int r = 1; r <= numOfDays; r++) {
                for (int c = 0; c < numOfDays; c++) {
                    System.out.format("%11d\t",table[r][c]);
                }
                System.out.println();
            }
            
            // trace back to find solution
            System.out.println("Solution: the maximum number of zombies we can zap is " + table[1][0]);
            int dayCharge = 1;
            for (int c = 0; c < numOfDays-1;c++) {
                int score = table[dayCharge][c];
                if (score == table[dayCharge+1][c+1]) {
                        System.out.println("Day " + c + " : Hold your fire");
                        dayCharge++;
                }
                else {
                    System.out.println("Day " + c + " : FIRE!   Watch " + Math.min(32, Math.min(zombies[c],(int) Math.pow(2,dayCharge-1))) + " zombies fry!");
                    dayCharge = 1;
                }                    
            }
            System.out.println("Day " + (numOfDays-1) + " : FIRE!   Watch " + Math.min(32, Math.min(zombies[numOfDays-1],(int) Math.pow(2,dayCharge-1))) + " zombies fry!");
            
        }
    } // main
    
} // Brains class