За двома матрицями A та B ми можемо обчислити C = AB використовуючи стандартні правила множення матриць:

Кількість колонок у матриці A має співпадати з кількістю рядків матриці B. Позначимо через rows(A) та columns(A) відповідно кількість рядків та колонок у матриці A. Кількість множень, необхідних для обчислення матриці C (її кількість рядків співпадає з A, а кількість стовпчиків з B) дорівнює rows(A) * columns(B) * columns(A). Наприклад, якщо 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. Вивід має строго відповідати формату, наведеному у прикладі. Якщо існує декілька оптимальних порядків множення матриць, надрукуйте довільний з них.