У Поликарпа есть строка \(s\), которая состоит из строчных латинских букв. Он кодирует эту строку по следующему алгоритму:
Например, кодирование строки \(s\)=«codeforces» происходит так:
Таким образом, результатом кодирования строки \(s\)=«codeforces» является строка «serofedsoc».
Напишите программу, которая осуществляет декодирование — то есть по результату кодирования восстанавливает исходную строку \(s\).
Первая строка содержит одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных.
Первая строка каждого набора содержит одно целое число \(n\) (\(1 \le n \le 2 \cdot 10^5\)) — длину строки \(b\).
Вторая строка каждого набора содержит строку \(b\) длины \(n\), состоящую из строчных латинских букв — результат кодирования исходной строки \(s\).
Гарантируется, что сумма значений \(n\) по всем наборам входных данных в тесте не превосходит \(2 \cdot 10^5\).
Для каждого набора входных данных выведите строку \(s\) из которой был получен результат кодирования \(b\).
5 10 serofedsoc 3 ttf 9 tlrhgmaoi 1 w 15 hnndledmnhlttin
codeforces fft algorithm w meetinthemiddle
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач