Kim is playing a city-building simulation game on an infinite chessboard. Every cell is denoted by two integers $(x, y)$. Two cells are adjacent if they share an edge; formally, cell $(x, y)$ is adjacent to four cells: $\{(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)\}$.

In the beginning (day 0), city $i$ occupies the single cell $(x_i, y_i)$. If a cell is occupied by any city, it is called a developed cell. Thus, on day 0, there are exactly $N$ developed cells.

After each day, the city will grow and expand by occupying any undeveloped adjacent cells. Formally, for each city $i$, let $S_i$ be the set of cells adjacent to at least one cell in city $i$. Starting from city 1 to city $n$, any undeveloped cell in $S_i$ becomes part of city $i$ and becomes developed.

We call two cities $u, v$ "connected" when you can move between $(x_u, y_u)$ and $(x_v, y_v)$ by only passing through adjacent developed cells. For two cities $u, v$, let $f(u, v)$ be the first day on which cities $u$ and $v$ become connected.

Kim is interested in the values of $f(u, v)$, but there are too many values to consider. Thus, Kim only wants to calculate $\sum_{1 \le i < j \le N} f(i, j)$ for a given set of starting cells.

Input

The first line contains the number of cities $N$ ($1 \le N \le 250000$).

In the next $N$ lines, the position of the $i$-th city's starting cell is given as two integers $x_i, y_i$ ($-10^7 \le x_i, y_i \le 10^7$).

All given cells are distinct.

Output

Print $\sum_{1 \le i < j \le N} f(i, j)$, where $f(i, j)$ is the first day on which cities $i$ and $j$ become connected.

Examples

Input 1

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

Output 1

19

Input 2

3
0 2
4 0
0 0

Output 2

5

Note

In Day 0 : 100000 000000 300020 In Day 1 : 110000 100020 330222 In Day 2 : 111020 110222 332222 $f(1, 2) = 2, f(1, 3) = 1, f(2, 3) = 2$. Thus the answer is 5.