Počet sloupců matice A musí být stejný jako počet řádků matice B. Je zřejmé, že pro výpočet celé matice C je potřeba provést celkem operací násobení ( udává počet řádků matice X, udává počet sloupců matice X). Například pokud by A byla matice a B matice , násobení těchto matic by si vyžádalo celkem 10 . 15 . 20 neboli 3000 dílčích operací násobení.

Pro násobení více než dvou matic existuje více způsobů, jak to provést. Například pro matice X, Y, Z můžeme spočítat buď jako , nebo . Předpokládejme, že X je matice , Y je matice a Z je matice . Podívejme se na počty dílčích operací násobení pro jednotlivé varianty pořadí:

• 5 . 20 . 10 = 1000 operací násobení pro určení mezivýsledku , matice .
• 5 . 35 . 20 = 3500 operací k určení konečného výsledku.
• Celkový počet operací násobení je tedy 4500.

• 10 . 35 . 20 = 7000 operací násobení pro určení mezivýsledku , matice .
• 5 . 35 . 10 = 1750 operací k určení konečného výsledku.
• Celkový počet operací násobení je tedy 8750.

Je zřejmé, že první způsob výpočtu je efektivnější.

Vaším úkolem je pro danou posloupnost matic určit optimální pořadí jejich násobení tak, aby celkový počet dílčích operací násobení byl minimální.

Specifikace vstupu

Vstup se skládá z N zadání. První řádek vstupu obsahuje pouze celé kladné číslo N. Dále následují jednotlivá zadání. Na prvním řádku každého zadání je jedno kladné celé číslo M udávající počet matic. Následuje M řádků, na každém z nich je dvojice kladných celých čísel udávající počet řádků a počet sloupců (v tomto pořadí) matice. Pořadí, v jakém jsou řádky s rozměry matic uspořádány, odpovídá uspořádání matic až . Hodnota M nebude nikdy větší než 10 a menší než 2.

Specifikace výstupu

Výstupem programu bude jedna řádka pro každé zadání obsahující uzávorkovaný výraz, ze kterého jasně vyplývá pořadí násobení matic. Výrazem je `(E x E)', kde E je buď výraz, nebo označení matice. Přesný formát výstupu viz též níže uvedený příklad.

Pokud existuje více řešení, libovolné z nich bude akceptované jako správná odpověď.

Příklad vstupu

3
3
1 5
5 20
20 1
3
5 10
10 20
20 35
6
30 35
35 15
15 5
5 10
10 20
20 25

(A1 x (A2 x A3))
((A1 x A2) x A3)
((A1 x (A2 x A3)) x ((A4 x A5) x A6))