eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Babs` Box Boutique

Babs` Box Boutique

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Бэбс продает коробки, причем много. Все ее коробки прямоугольные, но бывают разных размеров. Бэбс хочет создать привлекательную пирамидку, укладывая коробки одну поверх другой за пределами своего магазина. Чтобы поддерживать аккуратность и стабильность, боковые стороны должны оставаться параллельными, она никогда не положит коробку поверх другой, если верхняя коробка выступает над нижней. Например, ящик с основанием 5 - на - 10 не может быть помещен на коробку с основанием 12 - на - 4.

Of course the boxes have three dimensions and Babs can orient the boxes anyway she wishes. Thus a 5-by-10-by-12 box may be stacked so the base is 5-by-10, 5-by-12, or 10-by-12.

For example, if Babs currently has 4 boxes of dimensions 2-2-9, 6-5-5, 1-4-9 and 3-1-1, she could stack up to 3 boxes but not all four. (For example, the third box, the first box, then the last box, appropriately oriented. Alternatively, the second box could replace the third (bottom) box.)

Babs' stock rotates, so the boxes she stacks outside change frequently. It's just too much for Babs to figure out and so she has come to you for help. Your job is to find the most boxes Babs can stack up given her current inventory. Babs will have no more than 10 different sized boxes and will use at most one box of any size in her display.

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

A positive integer n (n10) will be on the first line for each test case. Each of the next n lines will contain three positive integers giving the dimensions of a box. No two boxes will have identical dimensions. None of the dimensions will exceed 20. A line with 0 will follow the last test case.

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

For each test case, output the maximum number of boxes Babs can stack using the format given below.

Пример

Входные данные #1
4
2 2 9
6 5 5
1 4 9
3 1 1
3
2 4 2
1 5 2
3 4 1
0
Выходные данные #1
Case 1: 3
Case 2: 3
Источник 2012 ACM North America, East Central Regional Contest (ECNA), Problem A