SOLVE

LATER

Perfect Cubes

/

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.

**Addition Information**

**For 20 points: **\(4 <= N <= 50\), \(1 <= K_{i} <= 25\), \(1 <= P_{j} <= 20\)

**For 100 Points**: Original constraints.

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

Initializing Code Editor...