题目描述

丹妮卡是一名画家，她想要作画，但目前没有任何颜料。

本题中每种颜色用一个正整数表示。给定整数数组 colors，代表作画所需要用到的全部颜色。

商店可以提供任意正整数颜色且数量无限，丹妮卡可以先购买若干种颜色；之后可以通过混合已有颜色得到新颜色。

混合规则：每次只能混合两种颜色 $A,B$，混合后得到新颜色 $A \text{ XOR } B$。通过混合得到的颜色可以继续参与后续混合调配。

允许购买不需要的颜色，要求购买的不同颜色数量尽可能少。求最少需要购买多少种颜色，才能调配出 colors 中所有需要的颜色。

输入格式

第一行一个整数 $n$，表示颜色数量。 第二行 $n$ 个整数，依次给出所需的每种颜色。

输出格式

输出一行一个整数，表示最少需要购买的颜色种数。

样例输入输出

样例 1 输入：

3
1 7 3

输出：

3

样例 2 输入：

15
534 251 76 468 909 410 264 387 102 982 199 111 659 386 151

输出：

10

样例 3 输入：

9
4 8 16 32 64 128 256 512 1024

输出：

9

数据范围

• (1 \le n \le 50)
• (1 \le colors_i \le 10^9)
• 数组中所有元素互不相同

提示

异或（XOR）是一种针对两个数字的二进制运算。首先将位数较短的二进制数高位补前导零，使两个数的二进制位数保持一致。随后按位计算：两个数字对应二进制位不同时，结果该位为 1；对应位相同时，结果该位为 0。

举例说明 (15 \text{ XOR } 55) 的运算过程： 先将两数转为二进制：15 是 1111，55 是 110111。给位数更短的 15 高位补零，补齐到相同位数，变为 001111。接着计算：001111 XOR 110111 = 111000（仅在两数二进制位不同的位置结果为 1）。最后将二进制结果转回十进制：111000 等于 56，因此 (15 \text{ XOR } 55 = 56)。