//{ Driver Code Starts //Initial Template for Java import java.io.*; import java.util.*; class GFG { public static void main(String args[])throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(in.readLine()); while(t-- > 0){ int N = Integer.parseInt(in.readLine()); String input_line[] = in.readLine().trim().split("\\s+"); int arr[]= new int[N]; for(int i = 0; i < N; i++) arr[i] = Integer.parseInt(input_line[i]); Solution ob = new Solution(); System.out.println(ob.matrixMultiplication(N, arr)); } } } // } Driver Code Ends //User function Template for Java class Solution{ static int matrixMultiplication(int n, int arr[]) { /* making a dp array for the gap strategy and to store answer of previous matrice multiplication 1)travelling the gap diagonals and handling trivial cases for 0 and 1 diagnol 2)handling for gap diagonals >= 2 */ int[][] dp = new int[n-1][n-1]; //1 for(int gap = 0 ; gap < n-1 ; gap++ ){ for(int i =0 , j = gap ; j < n-1 ; i++ ,j++){ if(gap == 0) dp[i][j] = 0; //i is first matrix , j is 2nd matrix else if(gap == 1) dp[i][j] = arr[i] * arr[j] * arr[j+1]; //2 else{ //k represents the cuts we are making from 0 to j-1 int min = Integer.MAX_VALUE; for(int k = i ; k < j ; k++){ //dp -> [i,k] = left half and [k+1,j] = right half //arr -> i*k+1 = left half , k+1*j+1 = right half int left = dp[i][k]; int right = dp[k+1][j]; int m = arr[i] * arr[k+1] * arr[j+1]; min = Math.min(min , left + right + m); } dp[i][j] = min; } } } return dp[0][n-2]; } }