apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Alice guesses the strings that Bob made for her.

At first, Bob came up with the secret string $$$a$$$ consisting of lowercase English letters. The string $$$a$$$ has a length of $$$2$$$ or more characters. Then, from string $$$a$$$ he builds a new string $$$b$$$ and offers Alice the string $$$b$$$ so that she can guess the string $$$a$$$.

Bob builds $$$b$$$ from $$$a$$$ as follows: he writes all the substrings of length $$$2$$$ of the string $$$a$$$ in the order from left to right, and then joins them in the same order into the string $$$b$$$.

For example, if Bob came up with the string $$$a$$$="abac", then all the substrings of length $$$2$$$ of the string $$$a$$$ are: "ab", "ba", "ac". Therefore, the string $$$b$$$="abbaac".

You are given the string $$$b$$$. Help Alice to guess the string $$$a$$$ that Bob came up with. It is guaranteed that $$$b$$$ was built according to the algorithm given above. It can be proved that the answer to the problem is unique.

## Input Format
The first line contains a single positive integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases in the test. Then $$$t$$$ test cases follow.

Each test case consists of one line in which the string $$$b$$$ is written, consisting of lowercase English letters ($$$2 \le |b| \le 100$$$) — the string Bob came up with, where $$$|b|$$$ is the length of the string $$$b$$$. It is guaranteed that $$$b$$$ was built according to the algorithm given above.

## Output Format
Output $$$t$$$ answers to test cases. Each answer is the secret string $$$a$$$, consisting of lowercase English letters, that Bob came up with.

## Examples
```input
4
abbaac
ac
bccddaaf
zzzzzzzzzz
```
```output
abac
ac
bcdaf
zzzzzz
```

## Note
The first test case is explained in the statement.

In the second test case, Bob came up with the string $$$a$$$="ac", the string $$$a$$$ has a length $$$2$$$, so the string $$$b$$$ is equal to the string $$$a$$$.

In the third test case, Bob came up with the string $$$a$$$="bcdaf", substrings of length $$$2$$$ of string $$$a$$$ are: "bc", "cd", "da", "af", so the string $$$b$$$="bccddaaf".

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a[0 \ldots n-1]$$$ of length $$$n$$$ which consists of non-negative integers. Note that array indices start from zero.

An array is called good if the parity of each index matches the parity of the element at that index. More formally, an array is good if for all $$$i$$$ ($$$0 \le i \le n - 1$$$) the equality $$$i \bmod 2 = a[i] \bmod 2$$$ holds, where $$$x \bmod 2$$$ is the remainder of dividing $$$x$$$ by 2.

For example, the arrays [$$$0, 5, 2, 1$$$] and [$$$0, 17, 0, 3$$$] are good, and the array [$$$2, 4, 6, 7$$$] is bad, because for $$$i=1$$$, the parities of $$$i$$$ and $$$a[i]$$$ are different: $$$i \bmod 2 = 1 \bmod 2 = 1$$$, but $$$a[i] \bmod 2 = 4 \bmod 2 = 0$$$.

In one move, you can take any two elements of the array and swap them (these elements are not necessarily adjacent).

Find the minimum number of moves in which you can make the array $$$a$$$ good, or say that this is not possible.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases in the test. Then $$$t$$$ test cases follow.

Each test case starts with a line containing an integer $$$n$$$ ($$$1 \le n \le 40$$$) — the length of the array $$$a$$$.

The next line contains $$$n$$$ integers $$$a_0, a_1, \ldots, a_{n-1}$$$ ($$$0 \le a_i \le 1000$$$) — the initial array.

## Output Format
For each test case, output a single integer — the minimum number of moves to make the given array $$$a$$$ good, or -1 if this is not possible.

## Examples
```input
4
4
3 2 7 6
3
3 2 6
1
7
7
4 9 2 1 18 3 0
```
```output
2
1
-1
0
```

## Note
In the first test case, in the first move, you can swap the elements with indices $$$0$$$ and $$$1$$$, and in the second move, you can swap the elements with indices $$$2$$$ and $$$3$$$.

In the second test case, in the first move, you need to swap the elements with indices $$$0$$$ and $$$1$$$.

In the third test case, you cannot make the array good.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
The store sells $$$n$$$ beads. The color of each bead is described by a lowercase letter of the English alphabet ("a"–"z"). You want to buy some beads to assemble a necklace from them.

A necklace is a set of beads connected in a circle.

For example, if the store sells beads "a", "b", "c", "a", "c", "c", then you can assemble the following necklaces (these are not all possible options):

And the following necklaces cannot be assembled from beads sold in the store:

The first necklace cannot be assembled because it has three beads "a" (of the two available). The second necklace cannot be assembled because it contains a bead "d", which is not sold in the store.

We call a necklace $$$k$$$-beautiful if, when it is turned clockwise by $$$k$$$ beads, the necklace remains unchanged. For example, here is a sequence of three turns of a necklace.

In particular, a necklace of length $$$1$$$ is $$$k$$$-beautiful for any integer $$$k$$$. A necklace that consists of beads of the same color is also beautiful for any $$$k$$$.

You are given the integers $$$n$$$ and $$$k$$$, and also the string $$$s$$$ containing $$$n$$$ lowercase letters of the English alphabet — each letter defines a bead in the store. You can buy any subset of beads and connect them in any order. Find the maximum length of a $$$k$$$-beautiful necklace you can assemble.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases in the test. Then $$$t$$$ test cases follow.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 2000$$$).

The second line of each test case contains the string $$$s$$$ containing $$$n$$$ lowercase English letters — the beads in the store.

It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$2000$$$.

## Output Format
Output $$$t$$$ answers to the test cases. Each answer is a positive integer — the maximum length of the $$$k$$$-beautiful necklace you can assemble.

## Examples
```input
6
6 3
abcbac
3 6
aaa
7 1000
abczgyo
5 4
ababa
20 10
aaebdbabdbbddaadaadc
20 5
ecbedececacbcbccbdec
```
```output
6
3
5
4
15
10
```

## Note
The first test case is explained in the statement.

In the second test case, a $$$6$$$-beautiful necklace can be assembled from all the letters.

In the third test case, a $$$1000$$$-beautiful necklace can be assembled, for example, from beads "abzyo".

Now solve the problem and return the code.