#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

int a[],dp[][];

//int pre[55][55];

// /* pre[i][j]=k 即 i到j之间由k断开

// 借此输出最小乘数的表达式 */

//void print_chain(int i, int j)

//{    // 递归输出最小连乘的表达式

//    if (i==j) printf("矩阵%d",i);

//    else

//    {

//        printf("(");

//        print_chain(i,pre[i][j]);

//        printf("*");

//        print_chain(pre[i][j]+1,j);

//        printf(")");

//    }

//}

int main()

{

    int t;

    while(~scanf("%d",&t))

    {

        while(t--)

        {

            int n; scanf("%d",&n);

            for(int i=;i<=n;i++)

            {

                int p,q; scanf("%d%d",&p,&q);

                if(i==) a[]=p;  a[i]=q;

            } // 第一个存行和列 之后的只存列

            //memset(pre,0,sizeof(pre));

            memset(dp,INF,sizeof(dp)); // 初始化无穷大

            for(int i=;i<=n;i++) dp[i][i]=;

            /// 只有本身一个矩阵时 矩阵乘积为0

            for(int i=;i<=n;i++) /// 枚举矩阵个数 由从小推大

                for(int l=;l<=n-i+;l++) /// 枚举左端下标

                {

                    int r=l+i-; // 根据个数 得到右端下标

                    dp[l][r]=dp[l+][r]+a[l-]*a[l]*a[r];

                    /// dp[l][r]视为 l矩阵*(dp[l+1][r])矩阵

                    //pre[l][r]=l;

                    for(int k=l+;k<r;k++)

                        dp[l][r]=min(dp[l][r],

                        dp[l][k]+dp[k+][r]+a[l-]*a[k]*a[r]);

                    /// dp[l][r]视为 (dp[l][k])矩阵*(dp[k+1][r])矩阵

                    // 当需要记录 pre[][] 时

//                    {

//                        int tmp=dp[l][k]+dp[k+1][r]+a[l-1]*a[k]*a[r];

//                        if(tmp<dp[l][r]) dp[l][r]=tmp, pre[l][r]=k;

//                    }

                }

//            for(int i=1;i<=n;i++)

//            {

//                for(int j=1;j<=n;j++)

//                    printf("%d ",pre[i][j]);

//                // printf("%d ",dp[i][j]);

//                printf("\n");

//            }

//            print_chain(1,n); // 最小连乘表达式

//            printf("\n");

            printf("%d\n",dp[][n]); // 最小连乘次数

        }

    }

    return ;

}