POLSKI SPOJ

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

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