1. 
import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 348 Optimal Array Multiplication Sequence
* Link: http://uva.onlinejudge.org/external/3/348.pdf
*
* @author Rolf Schirm
* @version 1.0, 04/10/2011
*
* Method :
http://algorithmen-und-problemloesungen.de/GAJ/programme/index.html
* Status : Accepted
* Runtime: 1.688
*/
public class Main {

private static int[] array;
private static int[] op, cl;
private static long[][] c;
private static int testCase;

private static void doProcess() {
int n = array.length - 1;
int i, j, k, p;

// Array mit Dummy-Werten initalisieren
for (j = 0; j < n; j++) {
for (i = 0; i < j; i++) {
c[i][j] = Long.MAX_VALUE;
}
c[j][j] = 0;
}

for (p = 1; p < n; p++) {
for (i = 0, j = p; j < n; i++, j++) {
for (k = i; k < j; k++) {
// Anzahl der Multiplikationen
long aux = c[i][k] + c[k+1][j] + array[i]*array[k+1]*array[j+1];

// Prüfen ob es ein neues Minimum ist
if (c[i][j] > aux) {
c[i][j] = aux;
c[j][i] = k;
}
}
}
}
}

private static void constructOrder(int i, int j) {
if ((j - i) > 1) {
int k = (int) c[j][i];
if (i != k) {
op[i]++;
cl[k]++;
}
if (k + 1 != j) {
op[k + 1]++;
cl[j]++;
}
constructOrder(i, k);
constructOrder(k + 1, j);
}
}

private static void write() {
// Anzahl der Matrizen
int n = array.length - 1;

// Ausgabe
String result = "Case " + testCase + ": (";

// Anzahl der Klammern bestimmen
constructOrder(0, n - 1);

for (int i = 0; i < n; i++) {
// Anzahl der öffnenden Klammern
for (int j = 0; j < op[i]; j++) {
result += '(';
}

// Matrix
result += "A" + (i+1);

// Anzahl der schließenden Klammern
for (int j = 0; j < cl[i]; j++) {
result += ')';
}

// Trennraum zwischen zwei Matrizen
result += " x ";
}

// Am Ende der Ausgabe " x " entfernen und eine Klammer hinzufügen
System.out.println(result.substring(0, result.length()-3) + ")");
}

public static void main(String[] args) throws Exception {
final BufferedReader reader = new BufferedReader(new
InputStreamReader(System.in));

String line;

for(testCase = 1; (line = reader.readLine())!= null &&
!line.equals("0"); testCase++) {
// Anzahl der Matrizen im folgenden Testfall
int count = Integer.parseInt(line);

// Für n Matrizen müssen nur n+1 Elemente gespeichert werden,
// da die Anzahl Spalten von n gleich der Anzahl der Zeilen von n+1 ist:
// A D0
// D0 D1
// D1 D2
int length = count+1;
array = new int[length];
op = new int[length];
cl = new int[length];
c = new long[length][length];

for(int i = 1; i <= count; i++) {
line = reader.readLine();
String[] split = line.split(" ");
// Nur die Anzahl der Zeilen des ersten Elements im Array speichern
if(i == 1) {
array[0] = Integer.parseInt(split[0]);
}

// Spalten jedes Elements im Array speichern
array[i] = Integer.parseInt(split[1]);
}

// Minimale Anzahl der Multiplikationen berechnen
doProcess();

// Resultat ausgeben
write();
}
}
}