在一个完全由完美逻辑学家组成的岛屿上，每位岛民都戴着一顶写有正整数的帽子。每位岛民都能看到其他所有岛民帽子上的数字，但无法看到自己帽子上的数字。除了知道自己帽子上的数字是一个正整数外，岛民对自己帽子上的数字一无所知。

有一天，天空中出现了一条神秘的信息，写着：“存在三位不同的岛民，其中两人帽子上数字的异或（XOR）结果等于第三人帽子上的数字。”在这条信息出现后，岛民们安排了连续多天的会议，每天举行一次。在每次会议上，任何确信自己属于某个满足该信息的三元组的岛民都会举手。

假设岛民们不会撒谎也不会犯错，且每位岛民一旦能够确定自己属于某个三元组，就会立即举手，请问至少需要多少天，才会有岛民在会议上举手？

输入格式

第一行包含一个整数 $n$ ($3 \le n \le 25$)，表示岛民的人数。

接下来的 $n$ 行，每行包含一个整数 $a$ ($1 \le a < 2^{25}$)，表示岛民帽子上的正整数。

题目保证输入满足天空中的信息是真实的；即岛民帽子上的数字中至少存在一个三元组，使得其中一个帽子上的数字等于另外两个帽子上数字的异或值。

输出格式

输出一个整数，表示需要多少次每日会议，才能让某位岛民推断出自己的帽子属于某个异或三元组。可以证明，最终至少会有人举手。

样例

样例输入 1

3
1
2
3

样例输出 1

1

样例输入 2

11
9
1
14
2
11
7
6
7
6
5
3

样例输出 2

3