Լեռներ#522

Լեռներ

2 վայրկյան
512 մեգաբայթ
Very hard

Միստր 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}:

Որպեսզի իր կոնստրուկտորը դարձնի լեռ, նա կարող է կատարել հետևյալ գործողությունը ցանկացած քանակությամբ անգամ:

  1. վերցնել ցանկացած հատված ,

  2. վերցնել դրական ամբողջ թիվ (0 < x < 2^{30}), և մետաղադրամի արժեքով փոխել հատվածի բարձրությունը a_j := a_j \mid x (համար խորհրդանիշի բացատրությունը հասանելի է էջի ստորին մասում):

Միստր IP-ն չունի շատ մետաղադրամներ, այնպես որ այժմ նա հետաքրքրվում է, թե որքան քիչ մետաղադրամ է անհրաժեշտ, որպեսզի կարողանա դարձնել իր կոնստրուկտորը կրկին նման լեռին: Օգնեք նրան գտնել այս թիվը:

Input

Մուտքի առաջին տողը պարունակում է ամբողջ թիվ (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:

Output

Յուրաքանչյուր փորձարկման դեպքի համար արտածեք մեկ ամբողջ թիվ — Միստր IP-ի կոնստրուկտորը դարձնելու համար անհրաժեշտ մետաղադրամների նվազագույն քանակը:

Examples

Example 1

Loading
Loading

Note

խորհրդանիշը նշանակում է «բիթային 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-ն կարող է կատարել գործողությունը երկու անգամ.

  1. ընտրել հատված , և մետաղադրամի արժեքով, կատարել a_3 := 3 \mid 4 = 7:

  2. ընտրել հատված , և մետաղադրամի արժեքով, կատարել 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 հատկությանը, հետևաբար գործողություններ կատարելը անհրաժեշտ չէ

Scoring

  1. ( միավոր): n \le 5, a_i \le 15

  2. ( միավոր): a_i \le 2

  3. ( միավոր): a_i \le 63

  4. ( միավոր): n \le 100

  5. ( միավոր): առանց լրացուցիչ սահմանափակումների: