Automatic Friends

Interview

Time limit2sMemory limit1024 MB

Summary

Count pairs of triples that agree in exactly one coordinate and differ in the other two.

Level: Medium5 of 10
Topics: Hash map, Combinatorics, Math, Array
Solved: No attempts yet

Problem

A school for young programmers decided to build its own social network that automatically suggests potential friends to each user. When registering, every user takes a psychological test, and the results determine the values of three psychological characteristics for that user. Each characteristic value is a positive integer.

If two users differ in all three psychological characteristics, they will constantly quarrel, and if they match in two or three characteristics, they will be bored. So the only pairs of users who are potential friends are those that match in exactly one characteristic and differ in the other two.

Given $n$ triples $(a_i, b_i, c_i)$ of characteristic values for the users, write a program that finds the number of pairs of potential friends, that is, the number of index pairs $i < j$ for which exactly one of the three equalities $a_i = a_j$ , $b_i = b_j$ , $c_i = c_j$ holds.

Input

The first line of the input contains the number $n$ of users. Each of the next $n$ lines contains three positive integers $a_i$ , $b_i$ , and $c_i$ , the characteristic values of the $i$ -th user.

Output

The output must contain the required number of pairs of potential friends.

Hint

In the first example, the pairs of potential friends are users 1 and 2, and users 2 and 3. In both cases the users match in the first characteristic and differ in the second and third. Users 1 and 3 match in the first two characteristics, so they do not form a pair of potential friends.

Examples2

Example 1
Input
```
3
1 2 3
1 4 5
1 2 4
```
Expected output
```
2
```

Example 2

Input

4
100 100 100
100 100 100
100 99 99
99 99 100

Expected output