Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MACIERZE - Mnożenie macierzy

Jeśli macierz A ma rozmiar (a,b) (a wierszy i b kolumn) oraz macierz B ma rozmiar (b,c), to możemy, wykonując mniej więcej a*b*c operacji arytmetycznych, policzyć iloczyn macierzy A*B, który będzie macierzą o rozmiarach (a,c).

Twoim zadaniem jest wyznaczyć optymalne nawiasowanie w wyrażeniu

A_0 * A_1 * A_2 ... A_{n-1}
w tym sensie, aby liczba wykonywanych operacji arytmetycznych była minimalna. Na przykład iloczyn trzech macierzy A_0=(10,20), A_1=(20,3), A_2=(3,1) obliczając w sposób (A_0 A_1) A_2 daje aż 630 operacji arytmetycznych, a obliczając w sposób A_0 (A_1 A_2) daje tylko 260 operacji arytmetycznych.

Twoim zadaniem jest obliczyć optymalny koszt wymnożenia n macierzy o danych rozmiarach

Input

W pierwszym wierszu dana jest liczba T - określająca liczbę zestawów danych. Każdy zestaw danych zapisany jest w dwóch wierszach. W pierwszym wierszu podana jest jedna liczba całkowita dodatnia n - określająca liczbę macierzy do wymnożenia. Powedzmy są to macierze A_0, A_1, ..., A_{n-1}. W drugim wierszu zapisanych jest n+1 liczb naturalnych dodatnich p_0, p_1, ..., p_n określających rozmiary macierzy. Rozmiar macierzy A_i to (p_i, p_{i+1}). Możesz załozyć, że n < 200 oraz p_i < 1000

Output

Dla każdego zestawu danych odpowiedz jaki jest minimalny koszt wymnożenia danych macierzy.

Example

Input:
3
1
10 90
2
40 50 60
3
10 20 3 1

Output:
0
120000
260

Dodane przez:Rafal Nowak
Data dodania:2007-05-29
Limit czasu wykonania programu:0.293s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ERL GOSU JS-RHINO NODEJS PERL6 VB.NET
Pochodzenie:W³asne
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.