Shaking hands

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

Today is Gorwin’s birthday, so she holds a party and invites her friends to participate. She will invite n friends, for convenience, Gorwin numbers them from 1 to n. Some of them have known each other, But some of them have not. Those friends whose have known each other will shake hands with each other, and drink one cup of champagne. Gorwin wants to know how many cups of champagne she should prepare. Can you help her?

Input

Multiple test cases (about 30), the first line of each case contains an integer n which indicates Gorwin will invite n friends to her party.

Next n lines will give a n*n matrix, if a[i][j] is 1, then friend i and friend j have known each other, otherwise they have not known each other.

Please process to the end of file.

[Technical Specification]

All input entries are integers.

1<=n<=30

0<=a[i][j]<=1

a[i][i]=0;

a[i][j]=a[j][i] for i!=j

Output

For each case, output an integer which denotes total cups of champagne Gorwin should prepare in a single line.

Sample Input

2
0 0
0 0
3
0 0 1
0 0 0
1 0 0

Sample Output

4
8
HintFor the second case, Gorwin will shake hands with all her friends, then Gorwin drink three cups of champagne, each friends drink one cup. Friend 1 and friend 3 know each other,every of them drinks one cup again. So the total cups is 3+3+2=8. 

hujie

Source

BestCoder Round #42