连锁信是一种敦促收件人将其转发给尽可能多的联系人的消息,通常带有某种神秘的解释。当然,这只是迷信,你不信,但你的朋友都信。您知道今天将会有一封这样的信件流传,并且您想知道您会收到它多少次 - 当然,并不是您自己发送!
给定一个包含 n 个元素的字符串数组 f,它描述了您和 n - 1 个朋友之间的联系:如果 i 和 j 之间的人会互相发送消息,则第 i 个字符串 (f[i][j]) 的第 j 个字符为“1”,否则为“0”。第一个人开始向他的所有联系人发送这封信;每个第一次收到这封信的人都会将其发送给他所有的联系人。你是n人,收到信后没有转发。
计算您将收到的这封信的份数。
输入
输入的第一行包含一个整数 n (2 ≤ n ≤ 50) — 涉及的人数。接下来的 n 行包含 f 的元素,长度为 n 的字符串。 f 中的每个字符要么是“0”,要么是“1”。保证以下两个方程成立:对于所有 i、j (1 ≤ i, j ≤ n),f[i][j] = f[j][i],f[i][i] = 0。
输出
输出一个整数——您最终将收到的信件的份数。
示例
输入 #1
4 0111 1011 1101 1110
输出 #1
3
输入 #2
4 0110 1010 1100 0000
输出 #2
0
输入 #3
4 0101 1001 0001 1110
输出 #3
2
注意
在第一种情况下,每个人都会向每个人发送信件,因此您会收到所有三个朋友的副本。
在第二种情况下,你不认识这些人,所以他们不会用迷信的东西来打扰你。
在第三种情况下,您的两个朋友向您发送了这封信的副本,但第三个朋友不认识他们,因此他不受影响。