Alexander the Great (of Macedon) is considered one of history's most successful commanders. By the age of thirty, Alexander had created one of the largest empires of the ancient world - stretching from the Ionian Sea to the Himalayas. (extracted from Wikipedia)

It is a little known "fact" that, after most of the wars he fought were over, Alexander instructed his generals to choose a square-shaped territory of arbitrary size that they would like to control. Interestingly, after every general chose his territory, the person that received the task of fulfilling the generals' wishes, Philip, noticed something: there are more squares on the map than there are generals in Alexander's army.

As you can see from the drawing above, some of the squares can touch sides or even intersect, making more squares. We are interested in knowing the number of different squares that can be seen on the map that Philip received. Help us and write a program that, for a particular map, will read the side length and position of the squares that the generals drew, and will calculate and output the total number of squares that can be seen on the map. For example, for the first drawing shown above (the left one), your program should output 11 (it should find 2 squares with side length 1, 7 squares with side length 2 and 2 squares with side length 4).

Input

The first line of input contains one integer N (1 ≤ N ≤ 100) - the number of squares that the generals drew.

Each of the following N lines contains 3 integers: Xi, Yi (1 ≤ Xi, Yi ≤ 10000000) and Li (1 ≤ Li ≤ 10000000) - Xi and Yi are the coordinates of the lower-left corner of the i-th square, and Li is the length of the sides of the i-th square.

In test cases worth at least 30% of the full score, the squares that the generals drew will be in a form of a rectangular grid (look at the right drawing above). In those test cases, each individual cell of the grid will be a square given in the input.

Output

Your program should output exactly one integer - the number of squares that can be seen on Philip's map.

Constraints

Time limit: 2 seconds
Memory limit: 64 megabytes

Examples

input
9
1 1 2
3 1 2
5 1 2
1 3 2
3 3 2
5 3 2
5 3 2
4 1 1
6 4 2

output
11

input
12
1 1 3
4 1 3
7 1 3
10 1 3
1 4 3
4 4 3
7 4 3
10 4 3
1 7 3
4 7 3
7 7 3
10 7 3

output
20