Masala F

Xotira 32 MB Vaqt 2000 ms
14

Teskari Satrdan Kattaroq

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.

Kiruvchi ma'lumotlar:

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).

Chiquvchi ma'lumotlar:

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


Misollar
# input.txt output.txt
1
5
4
cpm
2
grib
10
kupitimilablodarbuz
1000000000
capybara
6
abacaba
cpm
birggrib
kupitimilablodarbuz
arabypaccapybara
abacaba
Izoh:

Oson