Skibidi String #13091
Sign in

Skibidi String

1 second
256 megabytes

For a string , let be the number of distinct, non-empty substrings of . For example, f(\mathtt{aab}) = 5: the substrings are , , , , .

You are given an integer and a binary string of length n-2, indexed as t_1, \ldots, t_{n-2}.

We call a string of length Skibidi if sliding a window of length across gives n-2 windows, and for every 1 \le i \le n-2 the -th window matches t_i:

f\!\left(s_i s_{i+1} s_{i+2}\right) \bmod 2 = t_i.

Determine the lexicographically smallest Skibidi string consisting of lowercase English letters.

^\daggerModulo operation. For positive integers and , u \bmod v denotes the remainder when is divided by .

For example, for s = \mathtt{aabcba} we have important ! : must solve with O(3^6*n) dp

\big(f(\mathtt{aab}) \bmod 2,\ f(\mathtt{abc}) \bmod 2,\ f(\mathtt{bcb}) \bmod 2,\ f(\mathtt{cba}) \bmod 2\big) = (1, 0, 1, 0),

so t = \mathtt{1010}, i.e. t_1=1,\ t_2=0,\ t_3=1,\ t_4=0.

Input

The first line contains a single integer (1 \le T \le 10^4) — the number of test cases.

The first line of each test case contains an integer (3 \le n \le 2 \cdot 10^5) — the length of the required string.

The second line of each test case contains a binary string of length n-2 (t_i \in \{\mathtt{0}, \mathtt{1}\}).

It is guaranteed that the sum of over all test cases does not exceed 2 \cdot 10^5.

Output

For each test case, print the lexicographically smallest string consisting of lowercase English letters that satisfies the conditions.

Examples

Example 1

Loading
Loading

Note

For the first test case, s = \mathtt{aabcba}:

  • i = 1: has f = 5 distinct non-empty substrings, so f \bmod 2 = 1.

  • i = 2: has f = 6 distinct non-empty substrings, so f \bmod 2 = 0.

  • i = 3: has f = 5 distinct non-empty substrings, so f \bmod 2 = 1.

  • i = 4: has f = 6 distinct non-empty substrings, so f \bmod 2 = 0.

Hence the resulting is , as required.

For the second test case, s = \mathtt{abcbaa}:

  • i = 1: has f = 6 distinct non-empty substrings, so f \bmod 2 = 0.

  • i = 2: has f = 5 distinct non-empty substrings, so f \bmod 2 = 1.

  • i = 3: has f = 6 distinct non-empty substrings, so f \bmod 2 = 0.

  • i = 4: has f = 5 distinct non-empty substrings, so f \bmod 2 = 1.

Hence the resulting is , as required.

For the third test case, s = \mathtt{aaabcaa}:

  • i = 1: has f = 3 distinct non-empty substrings, so f \bmod 2 = 1.

  • i = 2: has f = 5 distinct non-empty substrings, so f \bmod 2 = 1.

  • i = 3: has f = 6 distinct non-empty substrings, so f \bmod 2 = 0.

  • i = 4: has f = 6 distinct non-empty substrings, so f \bmod 2 = 0.

  • i = 5: has f = 5 distinct non-empty substrings, so f \bmod 2 = 1.

Hence the resulting is , as required.

Scoring

  1. Subtask ( points) : (t=\mathtt{00000 \ldots 0})

  2. Subtask ( points) : (t=\mathtt{11111\ldots 1})

  3. Subtask ( points) : (1 \le \sum n \le 1000)

  4. Subtask ( points) : (1 \le \sum n \le 10^4)

  5. Subtask ( points): No additional constraints