Children like to build towers using blocks. All blocks are of cuboid form but their size might be different. We assume that the towers are built in such a way that each level has only one block. To build a firm tower, a block can be put on another block only when the length (resp. the width) of the former does not exceed the length (resp. width) of the latter. The block may be rotated in any orientation, so you can put any one of the six faces upward. Your mission is to write a program to calculate the height of the tallest firm tower. Note that to build the tallest tower, you may not want to use all the blocks.
The first line of the input file contains an integer indicating the number of test cases to follow. The first line of each test case contains a positive integer N (less than 50) indicating the number of blocks in the test case. Each of the following N lines will contain the description of one block. Each block is described by a sequence of three integer numbers (≤ 1000) which indicate the length of three dimensions of that block respectively.
For each test case in the input file, the output file must contain a line with a single integer, indicating the height of the tallest tower that may be built with the blocks in the corresponding test case.
2 3 1 2 3 2 4 2 1 3 5 7 1 1 2 2 3 3 3 5 2 3 3 3 1 7 4 2 4 1 4 5 2
10 21
Migrated from old NTUJ.
NCPC2007
| No. | Testdata Range | Score |
|---|