Perfect Cubes
/

## Hash function, Mathematics, Meet In the Middle, Number Theory, Primality test, Prime Factorization

Problem
Editorial
Analytics

You have $N$ numbers, $X_{1}, X_{2}, X_{3}, ... , X_{N}$. How many ways you can choose 4 numbers such that their product is a perfect cube. Formally, how many ways you can choose 4 integeres $a, b, c, d$ and $1 <= a < b < c < d <= N$ such that product of $X_{a} , X_{b}, X_{c}, X_{d}$ is a perfect cube.

A number $Z$ is said to be a perfect cube if there exists an integer $Y$ such that $Z = Y^3$.

Since the numbers can be quite large, so instead of giving a number directly, you will be given $K_{i}$  integers, $P_{1}, P_{2}, P_{3}, ... , P_{K}$. Formally, each number $X_{i}$  is a product of $P_{1}, P_{2}, P_{3}, ... , P_{K}$.

Input Format

First line will contain $N$
Each of next $N$ lines will start with $K_{i}$. Next $K_{i}$ integers $P_{1}, P_{2}, P_{3}, ... , P_{K}$  will be sperated by a space.

$4 <= N <= 1000$

$1 <= K_{i} <= 100$

$1 <= P_{j} <= 500$

Ouput Format

Print only one integer, which is many ways you can choose 4 numbers such that their product is a perfect cube.

For 20 points: $4 <= N <= 50$$1 <= K_{i} <= 25$$1 <= P_{j} <= 20$

For 100 Points: Original constraints.

SAMPLE INPUT
6
2 2 1
1 3
3 3 1 1
2 3 2
3 3 1 1
3 2 3 2

SAMPLE OUTPUT
3

Explanation

There are 6 numbers.

1st number = 2 x 1 = 2;

2nd number = 3

3rd number = 3 x 1 x 1 = 3

4th number = 3 x 2 = 6

5th number = 3 x 1 x 1 = 3

6th number = 2 x 3 x 2 = 12

So, you can choose {1st, 2nd, 3rd, 6th} and {1st, 2nd, 5th, 6th} and {1st, 3rd, 5th, 6th}. These are the 3 ways.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...