Ο Παντελής και ο Θησέας παίζουν ένα παιχνίδι με γραμματοσειρές. Ο Θησέας δίνει στον Παντελή μια γραμματοσειρά S και ένα ακέραιο X. Στόχος του Παντελή είναι να βρει μια μέγιστη υπακολουθία K της S, όπου πρέπει να ισχύουν όλοι οι πιο κάτω κανόνες:

• Η K θα εμφανίζεται στην αρχή της S.
• Η Κ θα εμφανίζεται στο τέλος της S.
• Η Κ δεν θα είναι πρόθεμα (prefix) της S, αλλά θα εμφανίζεται κάπου μέσα σε αυτήν χωρίς όμως να ξεπερνά το χαρακτήρα που βρίσκεται στη θέση Χ (Ξεκινώντας από το 1).

Για παράδειγμα, αν ο Θησέας δώσει στον Παντελή τα εξής:

lolaenalolmilolol 10

Ο Παντελής θα επιστρέψει σαν μέγιστη υπακολουθία Κ την lol επειδή:

• Η υπακολουθία Κ εμφανίζεται στη αρχή της S: lolaenalolmilolol (Κανόνας 1)

• Η υπακολουθία Κ εμφανίζεται στο τέλος της S: lolaenalolmilolol (Κανόνας 2)

• Η υπακολουθία Κ εμφανίζεται κάπου μέσα στην S, χωρίς να είναι το πρόθεμά της και χωρίς να ξεπερνά το χαρακτήρα που βρίσκεται στη θέση Χ=10: lolaenalolmilolol (Κανόνας 3)

Προσοχή: Αν δοθούν στον Παντελή τα εξής:

lollol 6

Θα επιστρέψει ξανά σαν απάντηση lol γιατί ισχύουν όλα τα πιο πάνω. Με άλλα λόγια η Κ μπορεί να είναι η κατάληξη (suffix) της S.

Δεδομένα εισόδου

• Στην πρώτη γραμμή θα εμφανίζεται ένας ακέραιος αριθμός Τ, το πλήθος των γραμματοσειρών που ακολουθούν.

• Σε κάθε μια από τις επόμενες Τ, γραμμές θα εμφανίζεται μια γραμματοσειρά S με πεζά γράμματα του λατινικού αλφαβήτου [a…z] και ένας ακέραιος Χ, χωρισμένα με κενό.

Περιορισμοί

1<=T<=10
1<=μέγεθος(S)<=10^6
1<=X<=μέγεθος(S)
Κάθε γραμματοσειρά S αποτελείται από πεζά γράμματα του λατινικού αλφαβήτου [a…z].