You have N numbers, X1,X2,X3,...,XN. 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 Xa,Xb,Xc,Xd is a perfect cube.
A number Z is said to be a perfect cube if there exists an integer Y such that Z=Y3.
Since the numbers can be quite large, so instead of giving a number directly, you will be given Ki integers, P1,P2,P3,...,PK. Formally, each number Xi is a product of P1,P2,P3,...,PK.
Input Format
First line will contain N.
Each of next N lines will start with Ki. Next Ki integers P1,P2,P3,...,PK will be sperated by a space.
4<=N<=1000
1<=Ki<=100
1<=Pj<=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<=Ki<=25, 1<=Pj<=20
For 100 Points: Original constraints.
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.