Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

strings

*800

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. String Similarity

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA binary string is a string where each character is either 0 or 1. Two binary strings $$$a$$$ and $$$b$$$ of equal length are similar, if they have the same character in some position (there exists an integer $$$i$$$ such that $$$a_i = b_i$$$). For example:

- 10010 and 01111 are similar (they have the same character in position $$$4$$$);
- 10010 and 11111 are similar;
- 111 and 111 are similar;
- 0110 and 1001 are not similar.

You are given an integer $$$n$$$ and a binary string $$$s$$$ consisting of $$$2n-1$$$ characters. Let's denote $$$s[l..r]$$$ as the contiguous substring of $$$s$$$ starting with $$$l$$$-th character and ending with $$$r$$$-th character (in other words, $$$s[l..r] = s_l s_{l + 1} s_{l + 2} \dots s_r$$$).

You have to construct a binary string $$$w$$$ of length $$$n$$$ which is similar to all of the following strings: $$$s[1..n]$$$, $$$s[2..n+1]$$$, $$$s[3..n+2]$$$, ..., $$$s[n..2n-1]$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 50$$$).

The second line of each test case contains the binary string $$$s$$$ of length $$$2n - 1$$$. Each character $$$s_i$$$ is either 0 or 1.

Output

For each test case, print the corresponding binary string $$$w$$$ of length $$$n$$$. If there are multiple such strings — print any of them. It can be shown that at least one string $$$w$$$ meeting the constraints always exists.

Example

Input

4 1 1 3 00000 4 1110000 2 101

Output

1 000 1010 00

Note

The explanation of the sample case (equal characters in equal positions are bold):

The first test case:

- $$$\mathbf{1}$$$ is similar to $$$s[1..1] = \mathbf{1}$$$.

The second test case:

- $$$\mathbf{000}$$$ is similar to $$$s[1..3] = \mathbf{000}$$$;
- $$$\mathbf{000}$$$ is similar to $$$s[2..4] = \mathbf{000}$$$;
- $$$\mathbf{000}$$$ is similar to $$$s[3..5] = \mathbf{000}$$$.

The third test case:

- $$$\mathbf{1}0\mathbf{10}$$$ is similar to $$$s[1..4] = \mathbf{1}1\mathbf{10}$$$;
- $$$\mathbf{1}01\mathbf{0}$$$ is similar to $$$s[2..5] = \mathbf{1}10\mathbf{0}$$$;
- $$$\mathbf{10}1\mathbf{0}$$$ is similar to $$$s[3..6] = \mathbf{10}0\mathbf{0}$$$;
- $$$1\mathbf{0}1\mathbf{0}$$$ is similar to $$$s[4..7] = 0\mathbf{0}0\mathbf{0}$$$.

The fourth test case:

- $$$0\mathbf{0}$$$ is similar to $$$s[1..2] = 1\mathbf{0}$$$;
- $$$\mathbf{0}0$$$ is similar to $$$s[2..3] = \mathbf{0}1$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/28/2024 01:10:59 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|