Uolevi goes to check up on Maija as she hasn't shown up in the tin foil hat club's gatherings in weeks. He finds her alone in a dark room, smearing her face against a red wall.

Maija has gone down the rabbithole trying to prove the existence of Illuminati. On her leads list board she has n pins and so much red yarn connecting them to one another that the blurry photos and old documents behind them can barely be seen. In this disoriented state, she has started counting the number of triangles formed by the yarn.

Uolevi decides to calculate the number of triangles where the end points are pins, tell Maija that number and then drag her out to get some fresh air. Help Uolevi calculate that number.

Input

The first line contains a single integer n. The i-th of next n lines contains a string s_i.

The j-th character of s_i is "1" if there is yarn connecting pins i and j and "0" otherwise.

Output

Print the number of triangles.

Constraints

• 1 \leq n \leq 3000
• |s_i| = n
• s_{i,j} \in \{0, 1\}
• s_{i, i} = 0
• s_{i, j} = s_{j, i}

Example 1

Input:

4
0111
1001
1001
1110

Output:

2

Example 2

Input:

5
01110
10111
11011
11101
01110

Output:

7