크기가 \(N \times M\)인 행렬 \(A\)와 \(M \times K\)인 행렬 \(B\)를 곱할 때 필요한 곱셈 연산의 수는 총 \(N \times M \times K\)번이다.

행렬 여러 개를 곱할 때는 곱하는 순서에 따라 곱셈 연산의 총 횟수가 달라지게 된다.

예를 들어, 크기가 \(10 \times 20\), \(20 \times 5\), \(5 \times 50\)인 세 행렬 \(A\), \(B\), \(C\)를 곱한다고 하자.

• \((AB)C\) 순서로 곱하면 연산 횟수는 \((10 \times 20 \times 5) + (10 \times 5 \times 50) = 1,000 + 2,500 = 3,500\)번이다.
• \(A(BC)\) 순서로 곱하면 연산 횟수는 \((20 \times 5 \times 50) + (10 \times 20 \times 50) = 5,000 + 10,000 = 15,000\)번이다.

주어진 행렬의 순서를 바꾸지 않고, 모든 행렬을 곱할 때 필요한 최소 곱셈 연산 횟수를 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 개수 \(T\)가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 행렬의 개수 \(N\)이 주어진다.

다음 \(N\)개의 줄에는 \(i\)번째 행렬의 크기를 나타내는 두 정수 \(r_i\)와 \(c_i\)가 공백으로 구분되어 주어진다.

\((1 \le T \le 10)\)

\((1 \le N \le 500)\)

\((1 \le r_i, c_i \le 500)\)

연속된 두 행렬 \(i\)번과 \(i+1\)번에 대해 \(c_i = r_{i+1}\) 조건이 항상 만족된다.

출력

각 테스트 케이스마다 주어진 모든 행렬을 곱하는 데 필요한 최소 곱셈 연산 횟수를 한 줄에 하나씩 출력한다.

제한사항

• 시간 제한: 2초
• 메모리 제한: 256MB

예제 입력 1

1
3
10 20
20 5
5 50

예제 출력 1

3500

예제 입력 2

2
3
10 20
20 5
5 50
4
10 100
100 5
5 50
50 1

예제 출력 2

3500