Pan IP pojechał w Karpaty, aby świętować swoje urodziny i przywiózł stamtąd pamiątkę — konstrukcję z klocków przypominającą kształtem górę.
Jednak podczas transportu do domu kilka elementów się zgubiło, a reszta przemieszała, więc teraz konstrukcja składa się z segmentów będących ustawionymi w rzędzie słupkami, z których -ty segment ma wysokość a_i. Pan IP chce, aby znów wyglądała jak góra, aby zachować wspomnienia z jego urodzin!
Konstrukcja składająca się z segmentów o wysokościach b_1, b_2, \dots, b_n wygląda jak góra, jeśli istnieje przynajmniej jeden indeks (1 \le m \le n), taki że dla każdego 1 \le i < m, b_{i} \le b_{i+1}, a dla każdego m < i \le n, b_{i-1} \ge b_{i}.
Aby konstrukcja znowu wyglądała jak góra, można wykonać następującą akcję dowolną liczbę razy:
wybrać dowolny segment ,
wybrać dodatnią liczbę całkowitą (0 < x < 2^{30}) i kosztem monet zmienić wysokość segmentu a_j := a_j \mid x (wyjaśnienie symbolu znajduje się na dole strony).
Pan IP nie ma zbyt wielu monet, więc teraz zastanawia się, ile minimalnie monet potrzebuje, aby móc sprawić, by jego konstrukcja znów wyglądała jak góra. Pomóż mu znaleźć tę liczbę!
Pierwsza linia wejścia zawiera liczbę całkowitą (1 \le t \le 5 \cdot 10^4) — liczbę przypadków testowych. Każdy przypadek testowy musi być rozwiązany niezależnie.
Pierwsza linia każdego przypadku testowego zawiera liczbę całkowitą (3 \le n \le 2 \cdot 10^5) — liczbę segmentów w konstrukcji.
Druga linia każdego przypadku testowego zawiera liczb całkowitych a_1, a_2, \dots, a_n (1 \le a_i < 2^{30}) — wysokości segmentów.
Gwarantuje się, że suma wartości we wszystkich przypadkach testowych nie przekracza 2 \cdot 10^5.
Dla każdego przypadku testowego wypisz jedną liczbę całkowitą — minimalną liczbę monet potrzebnych, aby konstrukcja pana IP wyglądała jak góra.
Przykład 1
Symbol oznacza operator "bitowego OR".
Bitowy OR dwóch liczb i działa w następujący sposób:
Rozważ reprezentację binarną p = \overline{(p_0 p_1 \dots p_{29})}_2 i q = \overline{(q_0 q_1 \dots q_{29})}_2, gdzie p_i, q_i \in \{0, 1\}, a p = \sum_{i=0}^{29} p_i \cdot 2^i oraz q = \sum_{i=0}^{29} q_i \cdot 2^i. Można wykazać, że takie reprezentacje są unikalne dla każdej liczby.
Wynik operacji r = \overline{(r_0 r_1 \dots r_{29})}_2 = \sum_{i=0}^{29} r_i \cdot 2^{i} oblicza się w następujący sposób:
r_i = p_i\ \textbf{or}\ q_i, gdzie jest zdefiniowane w następujący sposób:
Pierwszy Bit | Drugi Bit | Bit Wynikowy |
Na przykład,
jeśli p = 5 = \overline{(1010)}_2 i q = 12 = \overline{(0011)}_2, to p \mid q = \overline{(1011)}_2 = 13;
jeśli p = 6 = \overline{(011)}_2 i q = 7 = \overline{(111)}_2, to p \mid q = \overline{(111)}_2 = 7.
W pierwszym przypadku testowym pan IP może wykonać operację dwa razy:
wybrać segment i za koszt monet zmienić a_3 := 3 \mid 4 = 7.
wybrać segment i za koszt monety zmienić a_5 := 2 \mid 1 = 3.
Po tych operacjach konstrukcja wygląda następująco: [2, 5, 7, 8, 3, 3] z indeksem m = 4, spełniającym warunek a_1 \le a_2 \le a_3 \le a_4 \ge a_5 \ge a_6. Całkowity koszt wynosi 4+1 = 5. Można wykazać, że niemożliwe jest osiągnięcie celu przy mniejszym koszcie.
W drugim przypadku testowym pan IP może wykonać operację raz na segmencie , płacąc monety, aby zmienić a_2 := 1 \mid 2 = 3. Żadna operacja o koszcie nie może sprawić, że tablica będzie wyglądać jak góra; stąd jest to najmniejsza odpowiedź.
W trzecim przypadku segment z indeksem m = 5 już spełnia warunek a_1 \le a_2 \le a_3 \le a_4 \le a_5, więc nie są potrzebne żadne operacje
( punktów): n \le 5, a_i \le 15
( punktów): a_i \le 2
( punktów): a_i \le 63
( punktów): n \le 100
( punktów): brak dodatkowych ograniczeń.