Cənab IP doğum gününü qeyd etmək üçün Karpatiya Dağlarına getdi və oradan bir suvenir gətirdi — dağın formasını xatırladan bir konstrukt.
Lakin, evə gətirərkən bəzi hissələr itdi, buna görə də indi konstrukt seqmentdən ibarətdir, burada -ci seqmentin hündürlüyü a_i-dir. Cənab IP doğum gününün xatirələrini saxlamaq üçün konstruktunu yenidən dağa bənzətmək istəyir!
O düşünür ki, seqmentdən ibarət b_1, b_2, \dots, b_n hündürlükləri olan bir konstrukt dağa bənzəyir, əgər ən azı bir indeks (1 \le m \le n) varsa ki, burada hər 1 \le i < m, b_{i} \le b_{i+1}, və hər m < i \le n, b_{i-1} \ge b_{i}.
Konstruktunu dağa bənzətmək üçün, o aşağıdakı əməliyyatı istədiyi qədər edə bilər:
istənilən seqment -ni seç,
müsbət bir tam ədəd (0 < x < 2^{30}) seç və qəpiyə başa gələn seqmentin hündürlüyünü a_j := a_j \mid x ( simvolunun izahı səhifənin sonunda mövcuddur) dəyiş.
Cənab IP-nin çox qəpiyi yoxdur, buna görə də indi onun konstruktunu yenidən dağa bənzətmək üçün lazım olan ən kiçik qəpiyin sayını öyrənmək istəyir. Ona bu sayı tapmağa kömək edin!
Girişin birinci sətirində bir tam ədəd (1 \le t \le 5 \cdot 10^4) — test hallarının sayı. Hər bir test halı müstəqil olaraq həll edilməlidir.
Hər bir test halının birinci sətirində tam ədəd (3 \le n \le 2 \cdot 10^5) — konstruktun seqmentlərinin sayı.
Hər bir test halının ikinci sətirində tam ədəd a_1, a_2, \dots, a_n (1 \le a_i < 2^{30}) — seqmentlərin hündürlükləri.
Bütün test hallarının dəyərlərinin cəminin 2 \cdot 10^5-dən çox olmayacağı təmin edilir.
Hər bir test halı üçün bir tam ədəd çıxarın — Cənab IP-nin konstruktunu dağa bənzətmək üçün lazım olan ən kiçik qəpiyin sayı.
Example 1
simvolu "bitwise OR" operatorunu ifadə edir.
İki ədəd və üçün bitwise OR aşağıdakı kimi işləyir:
p = \overline{(p_0 p_1 \dots p_{29})}_2 və q = \overline{(q_0 q_1 \dots q_{29})}_2 binary təmsilini nəzərə alın, burada p_i, q_i \in \{0, 1\}, və p = \sum_{i=0}^{29} p_i \cdot 2^i və q = \sum_{i=0}^{29} q_i \cdot 2^i müvafiq olaraq. Belə təmsillərin hər bir ədəd üçün unikal olduğu göstərilə bilər.
Əməliyyatın nəticəsi r = \overline{(r_0 r_1 \dots r_{29})}_2 = \sum_{i=0}^{29} r_i \cdot 2^{i} aşağıdakı kimi hesablanır:
r_i = p_i\ \textbf{or}\ q_i, burada aşağıdakı kimi müəyyən edilir:
Birinci Bit | İkinci Bit | Nəticə Bit |
Məsələn,
əgər p = 5 = \overline{(1010)}_2 və q = 12 = \overline{(0011)}_2, onda p \mid q = \overline{(1011)}_2 = 13;
əgər p = 6 = \overline{(011)}_2 və q = 7 = \overline{(111)}_2, onda p \mid q = \overline{(111)}_2 = 7.
Birinci test halında, Cənab IP əməliyyatı iki dəfə həyata keçirə bilər:
seqment -ü seçir və qəpiyə a_3 := 3 \mid 4 = 7 edir.
seqment -i seçir və qəpiyə a_5 := 2 \mid 1 = 3 edir.
Bunlardan sonra konstrukt aşağıdakı kimi görünür: [2, 5, 7, 8, 3, 3] və m = 4 indeksi a_1 \le a_2 \le a_3 \le a_4 \ge a_5 \ge a_6 şərtini ödəyir. Ümumi xərc 4+1 = 5-dir. Daha kiçik xərc ilə məqsədə çatmağın mümkün olmadığını göstərmək olar.
İkinci test halında, Cənab IP bir dəfə seqment -də əməliyyat edə bilər, qəpiyə a_2 := 1 \mid 2 = 3 edir. qəpiyə array-ı dağa bənzətmək üçün heç bir əməliyyat mümkün deyil; buna görə də bu, ən kiçik cavabdır.
Üçüncü halda, m = 5 indeksi olan seqment artıq a_1 \le a_2 \le a_3 \le a_4 \le a_5 şərtini ödəyir, buna görə də heç bir əməliyyat etməyə ehtiyac yoxdur
( bal): n \le 5, a_i \le 15
( bal): a_i \le 2
( bal): a_i \le 63
( bal): n \le 100
( bal): əlavə məhdudiyyət yoxdur.