经过多年的努力,科学家们发明了一种全新的电子阅读器显示器。新的显示器具有更大的分辨率、消耗更少的能量并且其生产更便宜。此外,人们还可以弯曲它。唯一的不便是非常不寻常的管理。正是出于这个原因,开发人员决定将电子阅读器的软件留给程序员。
显示由 n × n 的像素正方形表示,每个像素可以是黑色或白色。显示行从左到右用 1 到 n 的整数编号,列从左到右用 1 到 n 的整数编号。显示器可以执行“x,y”等命令。当传统显示器执行此类命令时,它只是反转 (x, y) 的颜色,其中 x 是行号,y 是列号。但在我们的新显示器中,至少属于 (x, x) - (x, y) 和 (y, y) - (x, y) 段(包括两个段的两端)之一的每个像素都会反转颜色。
例如,如果最初尺寸为 5 × 5 的显示器是绝对白色的,则命令序列 (1, 4)、(3, 5)、(5, 1)、(3, 3) 会导致以下变化:
您是一名电子阅读器软件程序员,您应该计算显示图片所需的最少命令数。您可以将所有显示像素视为最初为白色。
输入
第一行包含数字 n (1 ≤ n ≤ 2000)。
接下来n行每行包含n个字符:需要显示的图片的描述。 “0”代表白色,“1”代表黑色。
输出
打印一个整数 z — 显示图片所需的最少命令数。
示例
输入 #1
5 01110 10010 10001 10011 11110
输出 #1
4