IOVID-114514 Infection

In the JOI Kingdom there are (N) palaces. The (i)-th palace is at coordinates ((X_i,Y_i)) and houses the (i)-th prince. At time (0), every prince starts moving in one of the four cardinal directions. Their motion is defined as follows:

• If a prince chooses to go east, his position at time \(t\) becomes \((x+t,\; y)\).
• If he goes west, his position becomes \((x-t,\; y)\).
• If he goes south, his position becomes \((x,\; y-t)\).
• If he goes north, his position becomes \((x,\; y+t)\).

Note that (t) can be any nonnegative real number.

Unfortunately, prince (1) is initially infected with the deadly IOVID-114514 virus at time (0). The virus only spreads when an infected prince and a healthy prince meet (i.e. have exactly the same coordinates at the same time). Once a prince is infected, he remains so forever.

You are allowed to choose the moving direction for each prince arbitrarily (each prince must fix his direction at time (0) and cannot change it later).

Determine the maximum number of infected princes at time (10^{100}) if you plan the directions of motion optimally.

A key observation is that if two princes are to meet at some positive time (T), then by writing out their positions we see that a necessary and sufficient condition for a meeting is one of the following:

• Horizontal meeting: Both princes choose horizontal moves and have \(Y_i = Y_j\) and take opposite directions (one east, one west). Then they meet at time \(T = \frac{|X_i-X_j|}{2}\).
• Vertical meeting: Both choose vertical moves with \(X_i = X_j\) and opposite directions (one north, one south); they meet at time \(T = \frac{|Y_i-Y_j|}{2}\).
• Diagonal meeting: One prince moves horizontally and the other vertically. In this case, if prince \(i\) is horizontal and prince \(j\) is vertical, then a meeting occurs if and only if \[ X_i + d_i T = X_j \quad \text{and} \quad Y_i = Y_j + d_j T, \] which implies \(T = d_i (X_j-X_i) = d_j (Y_i-Y_j)\) (with an appropriate choice of \(d_i,d_j\) in \(\{+1, -1\}\)). In other words, a necessary and sufficient condition is \(|X_j-X_i| = |Y_i-Y_j|\).

By appropriately assigning each prince one of the four directions, you can design a chain of meetings so that the infection spreads from prince (1) to as many princes as possible. In fact, one may show that the maximum number of infected princes is equal to the size of the connected component (containing prince (1)) in an undirected graph where each vertex represents a palace and an edge exists between two vertices (i) and (j) if and only if

• \(X_i = X_j\), or
• \(Y_i = Y_j\), or
• \(|X_i-X_j| = |Y_i-Y_j|\).

Your task is to compute this maximum number.

inputFormat

The first line contains an integer \(N\) \((1 \leq N \leq 1000)\), the number of palaces (and princes). Each of the next \(N\) lines contains two integers \(X_i\) and \(Y_i\) \((-10^9 \leq X_i,Y_i \leq 10^9)\), representing the coordinates of the \(i\)-th palace.

Note: It is possible that some palaces share the same coordinate.

outputFormat

Output one integer: the maximum number of infected princes at time \(10^{100}\).

sample

3
0 0
2 0
0 2

3