في عام 2077، يصبح إعداد المسائل أمراً بسيطاً. ستقوم الروبوتات بتوليد مسألة عن طريق تحديد بعض العمليات العشوائية ثم حلها. وما على واضع المسألة إلا التحقق مما إذا كانت المسألة صحيحة أم لا.

إليك مسألة من عام 2077:

معطى تبديل $p_1, p_2, \dots, p_n$، ومن المضمون أن $n$ عدد زوجي. ترغب في ترتيب هذا التبديل باستخدام نوع واحد فقط من العمليات:

• FakeSort(l,r): يجب أن تضمن أن $r - l + 1$ عدد زوجي. ليكن $k = r - l + 1$، عندئذٍ سيتم ترتيب أكبر $k/2$ عناصر وأصغر $k/2$ عناصر في المتتالية الجزئية المتصلة $p_l, p_{l+1}, \dots, p_r$ بشكل مستقل. أي، لتكن $L_1, L_2, \dots, L_{k/2}$ هي فهارس أكبر $k/2$ أعداد، و $S_1, S_2, \dots, S_{k/2}$ هي فهارس أصغر $k/2$ أعداد. نقوم أولاً بترتيب الأعداد الموجودة في الفهارس $L_1 \sim L_{k/2}$، ثم نرتب الأعداد الموجودة في الفهارس $S_1 \sim S_{k/2}$.

إليك مثالاً ملموساً؛ لنفترض أن التبديل هو $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$. إذا استدعينا FakeSort(2,7):

• $k = r - l + 1 = 6$. المتتالية الجزئية المتصلة $p_l, p_{l+1}, \dots, p_r$ هي $\{5, 7, 1, 8, 6, 4\}$؛ سنقوم بترتيب أكبر $3$ أعداد وأصغر $3$ أعداد في هذه المتتالية بشكل مستقل.
• $p = \{2, 5, \mathbf{7}, 1, \mathbf{8}, \mathbf{6}, 4, 3\}$؛ أكبر $3$ أعداد مكتوبة بخط عريض. بعد الترتيب تصبح $p = \{2, 5, \mathbf{6}, 1, \mathbf{7}, \mathbf{8}, 4, 3\}$.
• $p = \{2, \mathbf{5}, 6, \mathbf{1}, 7, 8, \mathbf{4}, 3\}$؛ أصغر $3$ أعداد مكتوبة بخط عريض. بعد الترتيب تصبح $p = \{2, \mathbf{1}, 6, \mathbf{4}, 7, 8, \mathbf{5}, 3\}$.

وبالتالي فإن $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$ بعد FakeSort(2,7) يصبح $\{2, 1, 6, 4, 7, 8, 5, 3\}$.

يرجى استخدام ما لا يزيد عن $114$ عملية لترتيب التبديل أو تحديد أن ذلك مستحيل. يمكن إثبات أنه إذا كان من الممكن ترتيب تبديل باستخدام هذه العملية، فهناك طريقة تستخدم ما لا يزيد عن $114$ عملية.

الإدخال

يحتوي الإدخال على عدة حالات اختبار. السطر الأول من الإدخال يحتوي على عدد صحيح $T$ ($1 \le T \le 10^3$)، وهو عدد حالات الاختبار.

لكل حالة اختبار، يحتوي السطر الأول على عدد صحيح زوجي $n$ ($4 \le n \le 10^5$)، وهو طول التبديل.

يحتوي السطر الثاني على $n$ أعداد صحيحة $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$)، وهي التبديل الذي تحتاج إلى ترتيبه. من المضمون أن $p$ يمثل تبديلاً.

من المضمون أن مجموع $n$ عبر جميع حالات الاختبار لا يتجاوز $2 \times 10^5$.

الإخراج

لكل حالة اختبار، إذا كان من المستحيل ترتيب التبديل، اطبع $-1$.

وإلا، اطبع عدداً صحيحاً $k$ ($0 \le k \le 114$) يمثل عدد العمليات المستخدمة.

في الأسطر الـ $k$ التالية، اطبع $l, r$ ($1 \le l \le r \le n$، و $r - l + 1$ عدد زوجي) في كل سطر، للإشارة إلى تنفيذ FakeSort(l,r).

أمثلة

مثال الإدخال 1

3
4
2 1 4 3
6
3 6 5 1 2 4
8
3 2 1 7 5 4 6 8

مثال الإخراج 1

1
1 4
-1
2
4 7
1 6