After IOI Ilya decided to make a business. He found a social network called "TheScorpyBook.com". It currently has N registered users. As in any social network two users can be friends. Ilya wants the world to be as connected as possible, so he wants to suggest friendship to some pairs of users. He will suggest user u to have a friendship with user v if they are not friends yet and there is a user w who is friends of both of them. Note that u, v and w are different users. Ilya is too busy with IPO these days, so he asks you to count how many friendship suggestions he has to send over his social network.

Input

The first line contains an integer number N — the number of users in the network. Next N lines containN characters each denoting friendship relations. j^th character if the i^th lines equals one, if users i and jare friends and equals to zero otherwise. This relation is symmetric, i.e. if user a is friend of b then b is also a friend of a.

Output

Output a single integer — number of friendship suggestions Ilya has to send.

Constraints

• 1 ≤ N ≤ 2000

Example

Input:
4
0111
1000
1000
1000

Output:
6

This question requires some insight , first of all we need to understand that  we need to send a suggestion to only that user which has a distance of 2 . For this (1)  we make an adjacency list of the given matrix

(2) we traverse the list for all i starting from i=0 to n and search if i need to send a suggest a friend request to j where j starts from i+1

  now for any user k that is adjacent to the present index i we just find if j is directly connected to the particular adjacent of i.  If it is then we increment the counter by 1 and break;

  This is evident from the portion 

 i 

                               if(frn[*it][j]=='1')

which clearly checks if the present adjacent of i is adjacent to j th node then we increase the count 

The final output is 2*cnt as we have counted for user i to j and not for j to i.

************* code runs her *******

#include<list>
#include<stack>
#include<iostream>
#include<stdio.h>
using namespace std;
char str[2020];
char frn[2010][2010];
int main()
{
 int n;
 cin>>n;
 list<int> li[2010];
 for(int i=0;i<n;i++)
 {
   cin>>str;
   for(int j=0;j<n;j++)
   {
       frn[i][j]=str[j];
       if(str[j]=='1')
    {
     li[i].push_back(j);
    }
   }
 }
int req=0;
 for(int i=0;i<n;i++)
 {
   for(int j=i+1;j<n;j++)
   {
    if(frn[i][j]=='0')
    {
     list<int> ::iterator it;
     for(it=li[i].begin();it!=li[i].end();it++)
     {
      if(frn[*it][j]=='1')
      {
       req++;
       break;
      }
     }
    }
   }
 }
 cout<<req*2<<endl;
 return 0;
}

      **** code ends here ******

The above thing can also be done using the concept of warshall where squaring the matrix will give us the number of walks of length 2 from i to j .   For more refer to warshall algorithm.

However squaring the matrix is o(n^3) complex but with binary matrices , this can be reduced using Four Russian Rule 

The setters code gives us the idea..

https://s3.amazonaws.com/codechef_shared/download/Solutions/COOK48/Setter/RRFRNDS.java