#2340 곱하기는 귀찮아

1 s   128 MB  

Description

 아주고등학교에 다니고있는 동이는 오늘 수학시간에 행렬을 배웠다. 학교를 마치고 수학선생님이 내주신 숙제를 해결하기위해 문제지를 펼친 동이는 너무 많은 문제 수에 깜짝 놀랐다. 곱하기 계산을 매우 귀찮아하는 동이의 눈 앞에는 수 많은 행렬의 곱하기 문제가 펼쳐져 있었다. 행렬의 곱하기라 함은 끝 없는 곱하기의 반복이 아니던가.

 숙제를 하고 싶지만, 숫자의 곱하기 연산은 최소한으로 하고 싶은 동이는 당신을 찾아왔다. 동이를 위하여 해당 행렬의 곱에서 최소로 계산해야할 곱하기 연산의 횟수를 계산하시오.

 아래의 상황을 생각해보자. 세 행렬 A(N×M), B(M×K), C(K×L)이 있다. 행렬은 결합법칙이 성립하므로 아래의 명제는 참이 된다.

 - 세 행렬 A, B, C에 대하여 A*B*C = (A*B)*C = A*(B*C) 이 성립한다.

 위에서 보듯이 행렬을 곱하는 순서에 상관없이 결과는 항상 일정하다. 하지만 행렬을 어떤 순서로 곱하느냐에 따라서 수행해야할 숫자의 곱 연산 횟수는 천차만별이다.

 예를 들어서, (A*B)*C를 계산하기 위해서는 (N*M*K) + (N*K*L)번의 연산을 필요로하지만, A*(B*C)를 계산하기 위해서는 (M*K*L) + (N*M*L)번의 연산을 필요로한다.

 그래서 동이는 행렬을 곱하는 순서를 바꿔서 최소의 연산으로 행렬의 곱을 계산하고 싶어한다. 동이를 위하여 행렬의 곱을 완성하기 위해 수행해야 할 연산의 최소 횟수를 계산해주자.

Input

가장 첫 줄에는 문제의 수 T(1<=T<=100)가 주어진다.

각 문제의 첫 줄에는 행렬의 수 N(1<=N<=100)이 주어진다.

이 후 N개의 행렬에 대한 행과 열 R, C가 차례로 주어진다. (1<=R,C<=100)

 

[ 입력 형식 ]

T

N

R C R C R C ...

N

R C R C R C ...

...

 

Output

 한 줄에 하나씩, 각 문제를 해결하기 위한 최소의 연산 횟수를 출력한다.

곱하기가 불가능한 문제인 경우 -1을 출력한다.

Sample Input

Sample Output

5
1
5 10
3
1 5 5 3 3 5
4
1 5 5 3 3 5 4 5
2
2 1 2 1 
2
4 6 4 4
0
30
-1
-1
-1

Source

김동이 (mitslll, 아주대학교)