Vova plays a very exciting game on the computer, which is called "Robot and Treasure." In this game on an endless checkered field in some cells treasure chests are located. The player is invited to control the robot, which must first be put in one of the cells, and then collect all the treasures. The robot takes valuable material objects when it is with them in one cell. The robot can move to any of the 8 neighboring cells. He does this by pressing a special key on the keyboard.

Recently, Vova suffered trouble. He lost several keys on the keyboard, but he still managed to collect all the treasures. Now Vova is interested in the question of how many keys he can spoil so that he can still be able to collect all the treasures.

Input

First line contains one integer n (1 ≤ n ≤ 1000) - number of boxes with jewels. Next given n lines, 2 integers in a line - the coordinates of the next chest. These numbers do not exceed 105 by absolute value.

Output

Print one number - the maximum number of keys that can be spoiled.