Kevin, the Snipe, and her children (apparently Kevin is a girl) were reunited, all thanks to Russell and Mr. Fredricksen! Now the two humans have embarked to their next adventure, towards Poland, but Kevin just noticed her children stole Mr. Fredricksen's cane without him realizing. It must be returned before they go too far away!

Kevin is not sure where they are now, but knows they went with their flying house somewhere to the northeast, and has narrowed it down to a few points where they might be resting. She will send some of her children to warn them of the missing cane. Each snipe can check multiple places, but since the house should be flying again soon, they can't waste any time and should always move to the north and/or to the east. Additionally, she wants to send the minimum number possible as long as every location on her list is visited.

Your job is to help her determine this number.

Input

Input consists of several test cases. 

Each test case begins with a single integer N (1 ≤ N ≤ 1000), the number of places the house can be.

N lines follow, each containing two integers, e_i and n_i, the distance (in miles) to the east and to the north, respectively of the i^th place related to Kevin's position. 0 ≤e_i, n_i ≤= 10000.

Input is terminated by a line containing a single integer zero.

Output

For each test case output a single integer: the minimum number of snipes needed to reach every place.

Example

Input:
5
1 1
2 2
3 3
4 4
5 5
5
1 5
2 4
3 3
4 2
5 1
5
0 1
1 1
1 2
2 2
2 3
0

Output:
1
5
1