Under construction

Still being built. Things may change

Greeting Card

Time limit2sMemory limit512 MB

Summary
Count how many pairs of given lattice points lie exactly 2018 units apart.
Level

Medium6 of 10

Topics
Hash map, Math, Geometry, Brute force
Solved
No attempts yet

Problem

Quido is sending a new year greeting to his friend Hugo, and he prints the card on a high precision plotter.

The plotter works in two steps. First it plots a pattern of nn dots on the paper. Then it draws a straight segment between every pair of dots that lie exactly 20182018 length units apart.

The plotter prints with a special holographic ink that is in short supply, so Quido wants to know how many segments the picture contains before he starts the job.

Input

The first line contains a positive integer nn, the number of plotted points. Each of the next nn lines contains two space separated integers, the coordinates of one point. Every coordinate is non-negative and smaller than 2312^{31}. There are at most 10510^5 points and all of them are distinct.

All coordinates and distances are given in plotter length units, and one unit in the x direction has the same length as one unit in the y direction.

Output

Print one integer, the number of pairs of points whose distance is exactly 20182018.

Examples2

  1. Example 1

    Input
    4
    20180000 20180000
    20180000 20182018
    20182018 20180000
    20182018 20182018
    
    Expected output
    4
    
  2. Example 2

    Input
    6
    0 0
    1680 1118
    3360 0
    5040 1118
    6720 0
    8400 1118
    
    Expected output
    5