All Tracks Data Structures Arrays Multi-dimensional Problem

Saul Goodman's Problem Statement
Tag(s):

Easy-Medium, Easy-Medium

Problem
Editorial
Analytics

Our favorite Lawyer Saul Goodman is busy saving lives of criminals. Then suddenly Mike comes into his office and gives him a problem which needs to be solved as soon as possible. Saul assures Mike that the problem will be solved within an hour. Mike questions him, "Who will solve this problem?".

In reply, Goodman says -

enter image description here

The problem statement is -

Given a 10^6 * 10^6 matrix with each cell initially consisting of zero values. The input given consists of co-ordinates of cells which have to be marked as 1. Let’s call them true cells. We have to find the number of pairs of such true cells which are in the same diagonal.

Can you help him out?

INPUT

The first line contains an integer 'T' denoting the total number of test cases. In each test case, the first line contains integer ‘N’ denoting the number of true cells in the matrix. The following N lines contain the location of the true cells.

OUTPUT

Print the total number of pairs of true cells which are in the same diagonal.

CONSTRAINTS

T=10
1<=N<=100000
1<=Coordinates of cells<=1000000

SAMPLE INPUT
2 
2 
8 5 
1 10 
5 
9 9 
3 5 
6 6 
2 8 
2 2
SAMPLE OUTPUT
0 
3
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications