У Владислава есть \(n\) неотрицательных целых чисел, и он хочет разделить их все на несколько групп так, чтобы в любой группе любая пара чисел не имела совпадающих значений битов среди битов от \(1\)-го до \(31\)-го (то есть рассматриваем \(31\) младший бит двоичной записи).
Для целого числа \(k\) пусть \(k_2(i)\) обозначает \(i\)-й бит в его двоичном представлении (справа налево, индексация с 1). Например, если \(k=43\), так как \(43=101011_2\), то \(43_2(1)=1\), \(43_2(2)=1\), \(43_2(3)=0\), \(43_2(4)=1\), \(43_2(5)=0\), \(43_2(6)=1\), \(43_2(7)=0\), \(43_2(8)=0, \dots, 43_2(31)=0\).
Формально, для любых двух чисел \(x\) и \(y\) в группе должно выполняться условие \(x_2(i) \neq y_2(i)\) для всех \(1 \leq i < 32\).
Какое минимальное количество групп Владу нужно, чтобы достичь своей цели? Каждое число должно попасть ровно в одну группу.
Примечание
В первом наборе входных данных любые два числа имеют одинаковые биты среди последних \(31\) бит, поэтому нам нужно поместить каждое число в свою собственную группу.
Во втором наборе входных данных \(a_1=0000000000000000000000000000000_2\), \(a_2=1111111111111111111111111111111_2\), таким образом, их можно поместить в одну группу, так как \(a_1(i) \ne a_2(i)\) для всех \(i\) от \(1\) до \(31\), включительно.