Codeforces Round 946 (Div. 3) |
---|
Finished |
Polycarp has a string $$$s$$$, which consists of lowercase Latin letters. He encodes this string using the following algorithm:
For example, encoding the string $$$s$$$="codeforces" happens as follows:
Thus, the result of encoding the string $$$s$$$="codeforces" is the string "serofedsoc".
Write a program that performs decoding — that is, restores the original string $$$s$$$ from the encoding result.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the string $$$b$$$.
The second line of each test case contains a string $$$b$$$ of length $$$n$$$, consisting of lowercase Latin letters — the result of encoding the original string $$$s$$$.
It is guaranteed that the sum of the values of $$$n$$$ over all test cases in the test does not exceed $$$2 \cdot 10^5$$$.
For each test case, output the string $$$s$$$ from which the encoding result $$$b$$$ was obtained.
510serofedsoc3ttf9tlrhgmaoi1w15hnndledmnhlttin
codeforces fft algorithm w meetinthemiddle
Name |
---|