ذهب السيد 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 بت" (bitwise 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
( نقاط): لا توجد قيود إضافية.