Алиса отгадывает строки, которые загадал ей Боб.
Сначала Боб придумал придумал секретную строку \(a\), состоящую из строчных букв латинского алфавита. Строка \(a\) имеет длину \(2\) или более символов. Затем по строке \(a\) он строит новую строку \(b\) и даёт Алисе строку \(b\), чтобы она могла угадать строку \(a\).
Боб строит \(b\) по \(a\) следующим образом: он выписывает все подстроки длины \(2\) строки \(a\) в порядке слева направо, а потом соединяет их в том же порядке в строку \(b\).
Например, если Боб загадал строку \(a\)=«abac», то все подстроки длины \(2\) строки \(a\) таковы: «ab», «ba», «ac». Следовательно, строка \(b\)=«abbaac».
Вам задана строка \(b\). Помогите Алисе определить строку \(a\), которую загадал Боб. Гарантируется, что \(b\) была построена по алгоритму, приведенному выше. Можно доказать, что ответ на задачу единственный.
Выходные данные
Выведите \(t\) ответов на наборы тестовых данных. Каждый ответ — это строка \(a\), состоящая из строчных букв латинского алфавита, которую загадал Боб.
Примечание
Первый набор тестовых данных разобран в условии.
Во втором наборе тестовых данных Боб загадал строку \(a\)=«ac», строка \(a\) имеет длину \(2\), поэтому строка \(b\) совпадает со строкой \(a\).
В третьем наборе тестовых данных Боб загадал строку \(a\)=«bcdaf», подстроки длины \(2\) строки \(a\) таковы: «bc», «cd», «da», «af», поэтому строка \(b\)=«bccddaaf».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
abbaac
ac
bccddaaf
zzzzzzzzzz
|
abac
ac
bcdaf
zzzzzz
|