Имея две матрицы A и B, мы можем вычислить C = AB используя стандартные правила умножения матриц:

Число колонок в матрице A должно совпадать с числом строк матрицы B. Пусть матрица A имеет размер m × n, матрица B имеет размер n × p. Тогда матрица С будет иметь размер m × p, а для ее вычисления следует совершить m * n * p умножений.

Например, если A имеет размер 10 × 20, B имеет размер 20 × 15, то необходимо совершить 10 × 20 × 15 = 3000 умножений для вычисления матрицы C.

Перемножать несколько матриц можно несколькими способами. Например, если у нас имеются матрицы X, Y и Z, то вычислить XYZ можно либо как (XY)Z, либо как X(YZ). Пусть X имеет размер 5 × 10, Y имеет размер 10 × 20, Z имеет размер 20 × 35.

Подсчитаем количество умножений, необходимых для перемножения трех матриц в каждом из этих двух случаях:

(XY)Z

• 5 × 20 × 10 = 1000 умножений для определения матрицы (XY), имеющей размер 5 × 20.
• Потом 5 × 35 × 20 = 3500 умножений для нахождения конечного результата.
• Общее количество умножений: 4500.

X(YZ)

• 10 × 35 × 20 = 7000 умножений для определения матрицы (YZ), имеющей размер 10 × 35.
• Потом 5 × 35 × 10 умножений для нахождения конечного результата.
• Общее количество умножений: 8750.

Очевидно, что при вычислении (XY)Z требуется меньшее количество умножений.

По заданной последовательности перемножаемых матриц следует найти оптимальный порядок их умножения. Оптимальным называется такой порядок умножения матриц, при котором количество элементарных умножений минимально.

Входные данные

Состоит из нескольких тестов. Первая строка каждого теста содержит количество n (n ≤ 10) перемножаемых матриц. Далее следуют n пар целых чисел, описывающих количество строк и столбцов в матрице, размеры матриц задаются в порядке их перемножения. Последний тест содержит n = 0 и не обрабатывается.

Выходные данные

Пусть матрицы пронумерованы A1, A2,..., An. Для каждого теста в отдельной строке следует вывести его номер и скобочное выражение, содержащее оптимальный порядок умножения матриц. Тесты нумеруются начиная с 1. Вывод должен строго соответствовать формату, приведнному в примере. Если существует несколько оптимальных порядков перемножения матриц, выведите любой из них.