Babs’ Box Boutique

Babs는 상자를 아주 많이 판다. 그녀의 상자는 모두 직육면체지만 크기는 제각각이다. Babs는 가게 밖에 상자를 하나씩 위로 쌓아 최대한 눈에 띄는 진열대를 만들고 싶어 한다. 깔끔함과 안정성을 위해 그녀는 항상 상자들의 옆면을 평행하게 맞추며, 위에 놓는 상자가 아래 상자 밖으로 삐져나오면 절대 올리지 않는다. 예를 들어 밑면이 $5 \times 10$인 상자는 밑면이 $12 \times 4$인 상자 위에 놓을 수 없다.

상자는 세 개의 치수를 가지며, Babs는 상자를 원하는 대로 어떤 방향으로든 놓을 수 있다. 따라서 $5 \times 10 \times 12$ 상자는 밑면이 $5 \times 10$, $5 \times 12$, 또는 $10 \times 12$가 되도록 쌓을 수 있다.

예를 들어 Babs가 현재 치수가 $2\text{-}2\text{-}9$, $6\text{-}5\text{-}5$, $1\text{-}4\text{-}9$, $3\text{-}1\text{-}1$인 상자 $4$개를 가지고 있다면, 네 개 모두는 아니지만 최대 $3$개까지 쌓을 수 있다. (예를 들어 세 번째 상자, 첫 번째 상자, 마지막 상자를 적절한 방향으로 쌓으면 된다. 또는 세 번째 상자 대신 두 번째 상자를 맨 아래에 놓아도 된다.)

Babs의 재고는 계속 바뀌므로 진열하는 상자도 자주 달라지는데, 이를 손으로 계산하기가 너무 벅차다. 여러분의 임무는 현재 재고로 Babs가 쌓을 수 있는 상자의 최대 개수를 구하는 것이다. Babs가 가진 서로 다른 크기의 상자는 $10$개를 넘지 않으며, 진열에는 각 크기의 상자를 최대 한 개만 사용한다.

입력에는 여러 개의 테스트 케이스가 있다. 각 테스트 케이스는 상자의 수인 양의 정수 $n$ ($n \le 10$)이 적힌 줄로 시작한다. 이어지는 $n$개의 줄에는 각각 한 상자의 세 치수가 양의 정수로 주어진다. 두 상자의 치수가 완전히 같은 경우는 없으며, 어떤 치수도 $20$을 넘지 않는다. 마지막 테스트 케이스 뒤에는 $0$ 하나만 있는 줄이 온다.

각 테스트 케이스마다 Case k: m 형식의 줄을 출력한다. 여기서 $k$는 ($1$부터 시작하는) 테스트 케이스 번호이고, $m$은 Babs가 쌓을 수 있는 상자의 최대 개수이다.