Нассер і Побітове АБО Масиву Рівного#12354

Нассер і Побітове АБО Масиву Рівного

2 секунди

256 мегабайтів

Легка

Нассер розмірковував про масиви і вирішив кинути собі виклик з побітовими операціями. Він створив наступне завдання:

Нассеру дано масив цілих чисел, і він хоче зробити всі елементи рівними.

Він може виконувати наступну операцію будь-яку кількість разів (можливо, нуль):

use xor basis

Оберіть індекс $i$ $(1 \leq i \leq n)$ (1 \le i \le n), виберіть ціле число $x$ $(1 \leq x \leq 1 0^{10})$ (1 \le x \le 10^{10}), і замініть $a_{i}$ a_i на $a_{i} ∣ x$ a_i \,|\, x.

Тут символ | представляє операцію побітове АБО. Для двох цілих чисел $p$ та $q$ , результат $p ∣ q$ є числом, у двійковому представленні якого стоїть $1$ в кожній позиції біта, де або $p$ , або $q$ мають $1$ . Наприклад, $5 ∣ 3 = 7$ 5 \,|\, 3 = 7, тому що $(101)_{2} ∣ (011)_{2} = (111)_{2}$ (101)_2 \,|\, (011)_2 = (111)_2.

Нассер запитав себе:

"Яка мінімальна кількість операцій потрібна, щоб зробити всі елементи масиву рівними?"

Вхідні дані

Кожен тест містить декілька тестових випадків. Перша стрічка містить одне ціле число $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) — кількість тестових випадків. Опис тестових випадків наступний.

Перша стрічка кожного тестового випадку містить одне ціле число $n$ $(1 \leq n \leq 2 \cdot 1 0^{5})$ (1 \le n \le 2 \cdot 10^5) — розмір масиву.

Друга стрічка кожного тестового випадку містить $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n $(1 \leq a_{i} \leq 1 0^{9})$ (1 \le a_i \le 10^9) — елементи масиву.

Гарантовано, що сума $n$ по всім тестовим випадкам не перевищує $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Вихідні дані

Для кожного тестового випадку виведіть одне ціле число — мінімальну кількість операцій, потрібних, щоб зробити всі елементи рівними.

Приклади

Приклад 1

Оцінювання

Підзавдання $1$ ( $10$ балів) : $(1 \leq a_{i} \leq 2)$ (1 \le a_i \le 2)
Підзавдання $2$ ( $20$ балів) : $(a_{i} = 2^{k})$ (a_i=2^k) тобто $a_{i}$ a_i є степенем $2$ .
Підзавдання $3$ ( $70$ балів) : Без додаткових обмежень.