A. UTPC Valentine's Gala
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The UTPC Valentine's Gala has just begun and the air is already buzzing with excitement! Burritos are in hand, people are coding, talking, and of course, wondering who they'll get to dance with.

Every guest at the gala has a secret list of people they are willing to dance with. To avoid any awkwardness on the dance floor, the Master of Ceremonies will only call a pair $$$(i, j)$$$ to the center of the room if the feeling is mutual—that is, guest $$$i$$$ wants to dance with guest $$$j$$$ and vice versa.

Being a UTPC officer, the Master of Ceremonies is very powerful and already knows everyone's secret list. They are now presenting it to you in the form of an $$$n \times n$$$ grid. Your task is to calculate the total number of unique couples that can be called down to the spotlight for a delightful dance!

Input

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 500$$$), the number of guests at the gala.

The next $$$n$$$ lines each contain $$$n$$$ space-separated integers, where the $$$j$$$-th integer in the $$$i$$$-th line denotes $$$A_{i,j}$$$ ($$$A_{i,j} \in \{0, 1\}$$$).

  • If $$$A_{i,j} = 1$$$, the $$$i$$$-th person is willing to dance with the $$$j$$$-th person.
  • If $$$A_{i,j} = 0$$$, they are not.

Note: $$$A_{i,i}$$$ will always be 0, as you cannot be your own dance partner.

Output

Output a single integer representing the total number of unique couples $$$(i, j)$$$ such that both people are willing to dance with each other.

Example
Input
4
0 1 1 0
1 0 0 1
0 1 0 1
0 1 0 0
Output
2
Note

Note that row 4 column 2 is 1 (person 4 would dance with person 2) and so is row 2 column 4 (person 2 would dance with person 4) thus (2, 4) is a valid couple. By the same logic, (1, 2) is also valid, so we have 2 valid couples.