Միստր IP-ը գնացել է Կարպատյան լեռներ՝ իր ծննդյան օրը նշելու և այնտեղից տուն բերել է մի сувենիր — մի կոնստրուկտոր, որը նման է լեռան ձևին:
Այնուամենայնիվ, տուն տանելու ընթացքում որոշ մասեր կորել են, այնպես որ այժմ կոնստրուկտորը բաղկացած է հատվածներից, որոնց -րդ հատվածի բարձրությունը a_i է: Միստր IP-ն ցանկանում է, որ այն կրկին նման լինի լեռան, որպեսզի պահի իր ծննդյան օրվա հիշողությունները:
Նա կարծում է, որ հատվածներից բաղկացած կոնստրուկտորը, որի բարձրությունները b_1, b_2, \dots, b_n են, նման է լեռան, եթե առնվազն մեկ ինդեքս (1 \le m \le n) գոյություն ունի, այնպես որ յուրաքանչյուր 1 \le i < m, b_{i} \le b_{i+1}, և յուրաքանչյուր m < i \le n, b_{i-1} \ge b_{i}:
Որպեսզի իր կոնստրուկտորը դարձնի լեռ, նա կարող է կատարել հետևյալ գործողությունը ցանկացած քանակությամբ անգամ:
վերցնել ցանկացած հատված ,
վերցնել դրական ամբողջ թիվ (0 < x < 2^{30}), և մետաղադրամի արժեքով փոխել հատվածի բարձրությունը a_j := a_j \mid x (համար խորհրդանիշի բացատրությունը հասանելի է էջի ստորին մասում):
Միստր IP-ն չունի շատ մետաղադրամներ, այնպես որ այժմ նա հետաքրքրվում է, թե որքան քիչ մետաղադրամ է անհրաժեշտ, որպեսզի կարողանա դարձնել իր կոնստրուկտորը կրկին նման լեռին: Օգնեք նրան գտնել այս թիվը:
Մուտքի առաջին տողը պարունակում է ամբողջ թիվ (1 \le t \le 5 \cdot 10^4) — փորձարկման դեպքերի քանակը: Յուրաքանչյուր փորձարկման դեպք պետք է լուծվի անկախ:
Յուրաքանչյուր փորձարկման դեպքի առաջին տողը պարունակում է ամբողջ թիվ (3 \le n \le 2 \cdot 10^5) — կոնստրուկտորի հատվածների քանակը:
Յուրաքանչյուր փորձարկման դեպքի երկրորդ տողը պարունակում է ամբողջ թվեր a_1, a_2, \dots, a_n (1 \le a_i < 2^{30}) — հատվածների բարձրությունները:
Հաստատվում է, որ բոլոր փորձարկման դեպքերի համար արժեքների գումարը չի գերազանցում 2 \cdot 10^5:
Յուրաքանչյուր փորձարկման դեպքի համար արտածեք մեկ ամբողջ թիվ — Միստր IP-ի կոնստրուկտորը դարձնելու համար անհրաժեշտ մետաղադրամների նվազագույն քանակը:
Example 1
խորհրդանիշը նշանակում է «բիթային OR» օպերատոր:
Երկու թիվ և համար բիթային OR-ը աշխատում է հետևյալ կերպ.
Հաշվի առեք p = \overline{(p_0 p_1 \dots p_{29})}_2 և q = \overline{(q_0 q_1 \dots q_{29})}_2 բիթային ներկայացումները, որտեղ p_i, q_i \in \{0, 1\}, և p = \sum_{i=0}^{29} p_i \cdot 2^i և q = \sum_{i=0}^{29} q_i \cdot 2^i համապատասխանաբար: Ցույց է տրվում, որ նման ներկայացումները յուրահատուկ են յուրաքանչյուր թվի համար:
Օպերացիայի արդյունքը r = \overline{(r_0 r_1 \dots r_{29})}_2 = \sum_{i=0}^{29} r_i \cdot 2^{i} հաշվարկվում է հետևյալ կերպ:
r_i = p_i\ \textbf{or}\ q_i, որտեղ սահմանվում է հետևյալ կերպ:
Առաջին Բիթ | Երկրորդ Բիթ | Արդյունքի Բիթ |
Օրինակ,
եթե p = 5 = \overline{(1010)}_2 և q = 12 = \overline{(0011)}_2, ապա p \mid q = \overline{(1011)}_2 = 13;
եթե p = 6 = \overline{(011)}_2 և q = 7 = \overline{(111)}_2, ապա p \mid q = \overline{(111)}_2 = 7:
Առաջին փորձարկման դեպքում, Միստր IP-ն կարող է կատարել գործողությունը երկու անգամ.
ընտրել հատված , և մետաղադրամի արժեքով, կատարել a_3 := 3 \mid 4 = 7:
ընտրել հատված , և մետաղադրամի արժեքով, կատարել a_5 := 2 \mid 1 = 3:
Այսներից հետո, կոնստրուկտորը տեսք ունի հետևյալը. [2, 5, 7, 8, 3, 3]՝ m = 4 ինդեքսով, որը բավարարում է a_1 \le a_2 \le a_3 \le a_4 \ge a_5 \ge a_6: Ընդհանուր արժեքը 4+1 = 5 է: Ցույց է տրվում, որ հնարավոր չէ հասնել նպատակին ավելի փոքր արժեքով:
Երկրորդ փորձարկման դեպքում, Միստր IP-ն կարող է կատարել գործողությունը մեկ անգամ հատվածում, վճարելով մետաղադրամ, որպեսզի a_2 := 1 \mid 2 = 3: արժեքով գործողություն չի կարող դարձնել զանգվածը լեռան տեսք, հետևաբար սա ամենափոքր պատասխանն է:
Երրորդ դեպքում, m = 5 ինդեքսով հատվածը արդեն բավարարում է a_1 \le a_2 \le a_3 \le a_4 \le a_5 հատկությանը, հետևաբար գործողություններ կատարելը անհրաժեշտ չէ
( միավոր): n \le 5, a_i \le 15
( միավոր): a_i \le 2
( միավոր): a_i \le 63
( միավոր): n \le 100
( միավոր): առանց լրացուցիչ սահմանափակումների: