Description

zty提出了一个奇怪的问题。

对于一个数列，若你每次选择区间[i,j],则你会花费$A_{i,j}$的代价，得知$A_i⊕A_{i+1}⊕......⊕A_j$的值。问至少花费多少代价，可以知道序列中的每一个数。

Input

第一行一个正整数，表示数列的长度。 。

接下来输入$n$行，每行$n$个整数。其中第$i$行第$j$个数为$A_{i,j}$，其含义见题目描述。

Output

输出一个整数，表示知道序列中每一个数的最小代价。

Samples

5
4 5 4 5 3 
2 3 1 5 2 
3 2 4 4 3 
4 2 4 5 0 
2 0 3 5 0

4

8
9662 17411 12297 3755 25882 15231 22822 21468 
1584 28544 15255 25709 4878 23151 24176 2099 
23816 19934 15431 16765 18174 9153 32661 10220 
1245 4059 24160 25989 29800 9590 22807 2565 
29497 25943 24766 10356 22018 26609 10314 29437 
25881 30681 9551 18685 564 12410 984 27482 
23409 29962 4502 19222 20377 21437 25662 9764 
26533 10552 16172 26234 2433 6216 31820 30567

15976

tips

【样例一解释】

一种最优的方案：选择区间【5,5】【5,2】【4,5】【2,1】【5,1】。

由区间【5,1】【5,2】可知序列中第一个数。

由于已知第一个数，结合区间【2,1】可知第二个数。

由区间【5,5】可知第五个数的大小。

由于已知第五个数，结合区间【4,5】可知第四个数。

由于已知第一、二、四、五个数，结合区间【1,5】可知第三个数。

此时代价总和为0+0+0+2+2=4。可以证明，4为最小的代价。

【样例二解释】

我有个绝妙的解释，可惜写不下。

【温习】 异或

异或是信息学竞赛中常见的考察点，符号为$⊕$。其通俗的表示为：相同则为假，相反则为真。

例如$x$的二进制表示是$0101$，$y$的二进制表示是$1011$，则$x⊕y=1110$。（按位对齐后每一位进行异或。$x$的最低位与$y$的最低位相同，异或结果对应为$0$，第二位不同，结果对应为$1$，其余同理）

显然异或满足交换律：$x⊕y=y⊕x$。

显然其也满足自反性：$x⊕x=0$。

显然有$x⊕0=x$。

数列$A_l$~$A_r$的异或和即$A_l⊕A_{l+1}⊕...⊕A_{r-1}⊕A_r$。特别地，当$l=r$时，异或和为$A_l(A_r)$本身。

在C++语言中，我们用^表示异或。以下代码：

c = a ^ b;

其含义为：将$a$与$b$异或的结果赋给$c$。

【数据范围及约定】

本题共有$10$个测试点，每个测试点10分，共100分。各测试点性质如下：

对于测试点$1$：$n\le 4$。

对于测试点$2$~$3$：$n\le 7$。

对于测试点$4$：输入保证$A$矩阵中的每个数都相等。

对于测试点$5$：输入保证$A$矩阵递增，即$A_{i,j}>A_{i,j-1}$，且$A_{i,1}>A_{i-1,n}$。

对于测试点$1$~$10$：$n\le 1000$，$0\le B_{i,j}\le 1\times 10^9$。不保证输入数据满足$A_{i,j}=A_{j,i}$。