Masala #O2P62MCCTX

Tabriklaymiz, siz Magistratura Yordam Markaziga qabul qilindingiz!
Biroq, darsda juda zerikib, hech narsa qilmaslikdan charchadingiz, shuning uchun o‘zingiz uchun o‘yin o‘ylab topdingiz.

Sizga satr s va juft butun son n beriladi. Siz unga ikkita turdagi amallarni qo‘llashingiz mumkin:

1. s satrining teskari o‘qilgan satrini s satrining oxiriga qo‘shish (masalan, agar s = cpm bo‘lsa, amal bajarilgandan keyin s = cpmmpc bo‘ladi).
2. Hozirgi s satrini teskari o‘qish (masalan, agar s = cpm bo‘lsa, amal bajarilgandan keyin s = mpc bo‘ladi).

Sizdan aynan n ta amal bajarilgandan keyin olinishi mumkin bo‘lgan leksikografik jihatdan eng kichik satrni aniqlash talab qilinadi. Amal turlarini har qanday tartibda qo‘llashingiz mumkin, lekin jami n ta amal bajarilishi shart.

Satr a satr b dan leksikografik jihatdan kichik bo‘lishi uchun quyidagilardan biri to‘g‘ri bo‘lishi kerak:

• a satri b satrining prefiksi bo‘lib, lekin ular teng emas;
• a va b satrlari birinchi farq qilgan joyda, a satridagi harf b satridagidan alifboda oldinda joylashgan bo‘ladi.

Birinchi qatorda butun son t (1 ≤ t ≤ 500) — testlar soni.

Keyin har bir test uchun quyidagilar beriladi:

• Bir qatorda juft butun son n (2 ≤ n ≤ 10^9) — bajariladigan amallar soni.
• Keyingi qatorda kichik lotin harflaridan tashkil topgan s satri (uzunligi 1 dan 100 gacha).

Har bir test uchun bittadan qatorda, aynan n ta amal bajarilgandan keyin olinishi mumkin bo‘lgan leksikografik jihatdan eng kichik satrni chiqarish kerak.