Tiling Up Blocks

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Michael The Kid receives an interesting game set from his grandparent as his birthday gift. Inside the game set box, there are n tiling blocks and each block has a form as follows:

Input

Several sets of tiling blocks. The inputs are just a list of integers.For each set of tiling blocks, the first integer n represents the number of blocks within the game box. Following n, there will be n lines specifying parameters of blocks in B; each line contains exactly two integers, representing left and middle parameters of the i-th block, namely, li and mi. In other words, a game box is just a collection of n blocks B = {b1, b2, . . . , bn} and each block bi is associated with two parameters (li,mi).
Note that n can be as large as 10000 and li and mi are in the range from 1 to 100.
An integer n = 0 (zero) signifies the end of input.

Output

For each set of tiling blocks B, output the number of the tallest tiling blocks can be made out of B. Output a single star \'*\' to signify the end of outputs.

Sample Input

3
3 2
1 1
2 3
5
4 2
2 4
3 3
1 1
5 5
0


Sample Output

2
3
*