Let's define a number ebne (even but not even) if and only if its sum of digits is…
- User
Let's define a number ebne (even but not even) if and only if its sum of digits is divisible by 2 but the number itself is not divisible by 2. For example, 13, 1227, 185217 are ebne numbers, while 12, 2, 177013, 265918 are not. If you're still unsure what ebne numbers are, you can look at the sample notes for more clarification.
You are given a non-negative integer s, consisting of n digits. You can delete some digits (they are not necessary consecutive/successive) to make the given number ebne. You cannot change the order of the digits, that is, after deleting the digits the remaining digits collapse. The resulting number shouldn't contain leading zeros. You can delete any number of digits between 0 (do not delete any digits at all) and n-1.
For example, if you are given s=222373204424185217171912 then one of possible ways to make it ebne is: 222373204424185217171912 → 2237344218521717191. The sum of digits of 2237344218521717191 is equal to 70 and is divisible by 2, but number itself is not divisible by 2: it means that the resulting number is ebne.
Find any resulting number that is ebne. If it's impossible to create an ebne number from the given number report about it. Input
The input consists of multiple test cases. The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer n (1 ≤ n ≤ 3000) — the number of digits in the original number.
The second line of each test case contains a non-negative integer number s, consisting of n digits.
It is guaranteed that s does not contain leading zeros and the sum of n over all test cases does not exceed 3000.
Output
For each test case given in the input print the answer in the following format:
- If it is impossible to create an ebne number, print "-1" (without quotes);
- Otherwise, print the resulting number after deleting some, possibly zero, but not all digits. This number should be ebne. If there are multiple answers, you can print any of them. Note that answers with leading zeros or empty strings are not accepted. It's not necessary to minimize or maximize the number of deleted digits.
Example
Input
4 4 1227 1 0 6 177013 24 222373204424185217171912
Output
1227 -1 17703 2237344218521717191
Note
In the first test case of the example, 1227 is already an ebne number (as 1 + 2 + 2 + 7 = 12, 12 is divisible by 2, while in the same time, 1227 is not divisible by 2) so we don't need to delete any digits. Answers such as 127 and 17 will also be accepted.
In the second test case of the example, it is clearly impossible to create an ebne number from the given number.
In the third test case of the example, there are many ebne numbers we can obtain by deleting, for example, 1 digit such as 17703, 77013 or 17013. Answers such as 1701 or 770 will not be accepted as they are not ebne numbers. Answer 013 will not be accepted as it contains leading zeroes.
Explanation:
- 1 + 7 + 7 + 0 + 3 = 18. As 18 is divisible by 2 while 17703 is not divisible by 2, we can see that 17703 is an ebne number. Same with 77013 and 17013;
- 1 + 7 + 0 + 1 = 9. Because 9 is not divisible by 2, 1701 is not an ebne number;
- 7 + 7 + 0 = 14. This time, 14 is divisible by 2 but 770 is also divisible by 2, therefore, 770 is not an ebne number.
In the last test case of the example, one of many other possible answers is given. Another possible answer is: 222373204424185217171912 → 22237320442418521717191 (delete the last digit).
Assistant
We need to solve: given digit string s of length n, we can delete any subset of digits (preserving order) to obtain a non-empty string without leading zeros (i.e., first digit cannot be '0'), such that the resulting integer (interpreted as string) is an ebne number: sum of digits even, and the integer is odd (i.e., last digit odd). So we need a substring (preserving order, but not necessarily contiguous because we can skip digits) that results in a number with these properties.
We can delete any digits, so we can essentially pick any subsequence of the original digit string. The constraints: the resulting subsequence must be non-empty, must not have leading zeros (first character != '0'), sum of digits must be even, and the last digit must be odd (1,3,5,7,9). If no such subsequence exists, output -1.
We need to output any valid subsequence.
We have t up to 1000, total n up to 3000, so overall length across test cases is small. We can likely do O(n) per test case or O(n^2) total.
We need to find any subsequence meeting conditions.
Observe: The last digit must be odd. So we need to include at least one odd digit as the last digit. Also sum of digits even. Also first digit cannot be '0'.
Simplify: Since we can delete any digits, we can think of constructing a subsequence: choose a starting digit (non-zero), then some middle digits, and an ending odd digit. Sum must be even.
We can just attempt to find a valid subsequence greedily.
First, note that we can keep the entire number if it meets the conditions: last digit odd, sum even, and no leading zero (by input, s has no leading zeros). So we can check whole string: if last digit odd and digit sum even -> output s. That's one quick case.
Otherwise, we need to remove some digits.
Observation: The property that the number is odd is solely determined by the last digit. So we need to end with an odd digit.
Also sum of digits even.
We can think: We have a sequence of digits; we can remove digits to adjust the parity of sum and also ensure last digit odd. Since we can delete arbitrary digits, we have flexibility.
We need a non-empty subsequence without leading zeros. So the first digit must be from an index where digit != '0', and we must include it as first.
We can treat the digits as array. Let's denote positions of odd digits (1,3,5,7,9). If there is no odd digit, impossible because last digit cannot be odd. So first condition: there must be at least one odd digit.
Also need sum even.
Given we have at least one odd digit, we can try to construct a subsequence that ends at that odd digit, and sum even. We can also delete digits to adjust sum parity. Since we can delete any digits, we can consider the sum of digits we include. Starting from first digit (non-zero) and including some digits up to an odd last digit. We want sum%2=0.
We can think: If we take the entire string but its sum is odd, we might delete one digit of odd parity (i.e., an odd digit) to flip sum parity. But careful: we need the last digit to be odd. So we can't delete the last digit if it's odd and we need it? Actually we could choose a different odd digit as last, not necessarily original last.
Better: We can start by selecting an odd digit as the last position. Then we need to select a subsequence that starts with some non-zero digit (could be the same as last if only one digit? But then sum is odd (since odd digit) so sum odd, not even. So need at least two digits unless we can have sum even from one digit? Single digit number: sum = digit. For it to be even, digit must even, but then last digit even => number even, not odd. So single digit cannot satisfy both: last digit odd implies sum odd. So need at least two digits.
Thus we need at least two digits, first non-zero, last odd, and total sum even.
We can try to find any subsequence meeting these conditions. Since n is small (<=3000 per test case, total 3000), we can try to construct a valid subsequence using simple logic.
One approach: We want to find a subsequence where sum even. We can consider all pairs of positions (i, j) with i <= j, digit[i] != '0', digit[j] odd, and sum of digits from i to j (of the subsequence? But we can skip digits, not necessarily contiguous. So we can choose any subset of digits between i and j. That gives flexibility: we can decide to include or exclude each digit to adjust parity.
Given a starting index i and ending index j (j >= i) where digit[i]!='0', digit[j] odd, we can include any subset of the other digits between i and j (including possibly none) to achieve sum parity even. Since we can also include digits after j? No, last digit is j so cannot include after. So we are restricted to indices up to j. But we could also include digits before i? No, first digit must be at i, so before i not included. So we only have digits from i to j inclusive, but we can choose a subsequence of them where the first is at i, last at j. We need to decide which of the intermediate digits to include.
The sum parity is parity of sum of chosen digits. Since we can choose any subset, we can achieve any parity as long as there is some flexibility? Actually given a set of numbers (digits), the parity of the sum of a subset can be any parity if we can adjust? Let's analyze: For a given set of digits (values 0-9), we can choose which to include. The parity of the sum is determined by parity of included digits: each digit contributes its own parity (digit%2). So the parity of the sum is XOR (or sum mod 2) of the parities of included digits. So essentially, the parity is the parity of the number of odd digits included (since even digits contribute 0 mod2). So we need to choose a subset of the digits from indices i..j (with forced inclusion of digit[i] and digit[j]) such that the total number of odd digits included is even (since we need sum even). Let parity_i = digit[i]%2, parity_j = digit[j]%2. Since digit[j] is odd, parity_j = 1. So we have at least one odd (j). We need total odd count mod2 = 0. So we need to include an even number of odd digits overall. Since we must include digit[i] and digit[j], we have base odd count = parity_i + 1 (since j odd) mod2. Actually parity_i may be 0 or 1. So base parity = (parity_i + 1) mod2. If parity_i is odd (1), then base = 1+1=2 => 0 mod2; if parity_i even (0), base = 0+1=1 mod2 = 1. So if digit[i] is even, base odd count = 1 mod2 -> we need an additional odd digit among the chosen intermediate digits to flip parity to 0. If digit[i] is odd, base odd count = 0 mod2 -> we already have even number of odds, so we can skip all intermediate digits (or include any number of even digits, but we must be careful: including extra odd digits would flip parity, so we would need to include an even number of extra odds to keep parity even, but we could also include none). So the condition for existence of a subsequence with start i and end j is:
-
If digit[i] is odd: we can simply take just digits i and j (skip all in between) provided i != j? But if i = j, then we have only one digit, which is odd, sum odd -> not allowed. So we need i < j. Taking just i and j: sum parity = odd+odd=even? Wait odd+odd = even mod2, yes. So that works (as long as i and j are distinct). So if we have an odd digit at position i (non-zero, obviously odd digits are non-zero except possibly 0? But 0 is even, so non-zero odd is fine) and another odd digit at position j>i, then the subsequence consisting of just those two digits yields an ebne number? Check: first digit digit[i] is non-zero (odd, so fine), last digit odd, sum even. So that's valid. But we must ensure that the resulting number does not have leading zeros; since digit[i] is odd, it's non-zero, okay. So any pair of odd digits with first before second gives a valid 2-digit number which is ebne. However, we must also ensure that after we delete digits, the order is preserved: we take digit[i] then digit[j] directly, so number = digit[i] followed by digit[j]. That is a subsequence of length 2. That works.
-
If digit[i] is even (non-zero because first digit can't be zero, so even digit can be 2,4,6,8), then base parity is 1. To achieve even parity, we need to include at least one additional odd digit among indices i+1..j-1 (since we need to flip parity). So we need to find any odd digit between i and j (exclusive). If there exists an odd digit k with i<k<j, then we can include it: take digit[i], that odd digit k, and digit[j] (maybe also other evens if we want but not needed). Then the odd digits count: digit[i] even (0), k odd (1), j odd (1) => total odds = 2 -> even. So that yields a valid ebne number (with length at least 3). However, we need to ensure the resulting number does not have leading zeros: digit[i] is non-zero even, fine. So existence condition: if we can find an even non-zero digit at some position i, and an odd digit at position j>i, and there is at least one odd digit strictly between them, then we have a solution. Alternatively, if we can start with an even digit and have two odd digits after it (one to be middle odd, one to be last), we can also use that.
But also we could start with a digit that is odd and find any later odd digit; that yields a solution. So the easiest path: if there are at least two odd digits in the whole string, can we always form a valid ebne? Not exactly: we need the first digit of our subsequence to be non-zero. If the first odd digit is at position i, we can take it as first and then later odd as last, that works. However, we must ensure the first digit we choose is not zero. Since odd digits are non-zero, that's fine. So if there are at least two odd digits, we can simply take the first odd digit and the last odd digit? But careful: we need the first digit in our subsequence to be the first odd we pick; but we might need to consider that there could be digits before that first odd that we skip. So yes, we can select the first odd digit we encounter (the leftmost odd) as the start, and any later odd digit as the end. That yields a 2-digit odd number? Example: s = "2 3 5"? Actually first odd is 3, last odd is 5 -> number "35", sum 8 even? 3+5=8 even, last digit 5 odd => ebne. So works. But what about s = "1 0 1"? first odd 1, last odd 1? Actually we need two distinct odd digits? If there are two odd digits, they can be same value but at different positions. That's fine. However, if there are exactly two odd digits but they are the same position? No, distinct positions. So okay.
But consider case: only one odd digit. Then we cannot use two odds. We need to construct a sequence where start is even non-zero, last is that odd, and we need an extra odd between them? But we have only one odd total, so impossible to have a middle odd. So we need to consider alternative: start with an odd? That would be the only odd, and we would need a later odd for last, but only one odd, so cannot. So with only one odd digit, the only way to have last digit odd is to end with that digit. Then we need sum even. We can include other digits (evens) to adjust parity. Since the odd digit contributes 1 mod2, we need the total number of odd digits included to be even. But we only have one odd (the last). So we need to include an additional odd digit, but there is none. So it's impossible to have even sum if we must include that odd digit as last and can't include any other odd. However, we might include the same odd digit only once; we cannot include it twice. So impossible. So with only one odd digit, no ebne subsequence exists? Wait, what if we start with an even digit (non-zero) and include that odd as last, and also include some even digits: odd count =1 -> sum odd, not even. So not possible. Could we start with a zero? No, leading zero not allowed. So indeed with exactly one odd digit, impossible.
But is there a scenario where we can have more than one odd but still no solution? Suppose we have two odd digits, but the first odd digit is at position i, but there is a leading zero issue? The first digit of the subsequence could be something else if we choose not to start with the first odd? But we could simply start with the first odd digit; it's non-zero. So that's fine. So two odd digits always yields a solution: take those two odds as the only digits. But check: the number formed by these two digits: if the first odd is at position i and second odd at j>i, then the number is digit[i]digit[j]. Is it guaranteed that the first digit is non-zero? Yes, odd digits are 1,3,5,7,9, all non-zero. So it's valid. Therefore, any string with at least two odd digits yields a valid ebne number.
But wait: what about the case where the string has at least two odd digits, but the first odd digit is not the leftmost digit? That's fine, we skip leading digits (which may be even or zero? Actually if there are leading zeros? Input s does not have leading zeros. So the very first digit is non-zero. But there could be zeros after. That's fine. So indeed any string with at least two odd digits works.
But is there any tricky case where the resulting number would have leading zero because we might choose a digit that is zero as first? We wouldn't. So okay.
Now, what about strings with zero odd digits? Then impossible because last digit must be odd. So impossible.
Thus, it seems the solution reduces to: if count_odd >= 2, then output some two odd digits (e.g., first and last odd, or first two odds). If count_odd == 0 or count_odd == 1, output -1.
But wait: sample test 3: n=6, s=177013. Let's count odds: digits: 1 (odd), 7 (odd), 7 (odd), 0 (even), 1 (odd), 3 (odd) -> that's 5 odds! So count_odd >=2, so according to this logic, we could output e.g., 17 (first two odds: 1 and 7) -> "17"? But "17" sum 8 even, last digit 7 odd, valid. However, sample output is 17703. So they output a longer number, but any two odds would be accepted. The problem statement says "If there are multiple answers, you can print any of them." So "17" should be acceptable. But we must check if "17" would be considered a valid subsequence? Yes, we can delete digits to get "17". However, is there any constraint about the resulting number not having leading zeros? "1" is fine. So "17" is valid. So why did sample output a longer number? Possibly to illustrate a specific answer, but "17" would be simpler. However, we need to verify the condition: the resulting number should not be empty and must not have leading zeros. "17" is fine.
But wait: sample input 1: 1227, count odd: 1,2,2,7 -> odds: 1 and 7 => two odds. So our rule says output any two odds: e.g., "17". But sample output is "1227" (the full number). Both are valid. So fine.
But test 2: 0 -> count_odd=0 => -1. Yes.
Test 4: long string with many odds, so two odds works.
So is it always sufficient? Let's think about edge cases: Could there be a scenario with exactly two odd digits where they are both odd but the subsequence of just those two digits might not be allowed because the first digit might be zero? But odd digits are never zero, so fine. However, what if the first odd digit is preceded by a zero? That's irrelevant because we skip it.
But what about the requirement that we cannot delete all digits; the resulting number must be non-empty. Two digits is non-empty.
Thus, the problem seems trivial: If the number of odd digits is at least 2, answer is any two odd digits (maybe the first two occurrences) concatenated. If less than 2, output -1.
But is that always correct? Let's double-check the definition: "ebne (even but not even) if and only if its sum of digits is divisible by 2 but the number itself is not divisible by 2." So number is odd. So last digit odd. Sum of digits even. That's all.
Now consider the case where there are two odd digits, but they are the same digit? That's fine. For example, "11": sum=2 even, last digit 1 odd, number 11 is odd. So valid.
What about case where there are two odd digits but the first odd digit is at the very end? That can't happen because the second odd must be after it. So if there are exactly two odds, the first odd is before the second odd. So taking those two yields a two-digit number with first digit odd, second digit odd. That's valid.
Now consider if there are two odd digits, but the first odd digit is the first character? That's fine.
Thus seems correct.
But wait: there is also condition that the resulting number must not contain leading zeros. Since odd digits are not zero, the first digit of our subsequence is an odd digit, so it's non-zero. So good.
Thus the answer is simple.
But why is the problem given with constraints up to 3000 and multiple test cases, and sample includes more complicated answers? Possibly because the initial reading might have a twist: The number s is a non-negative integer, but they say "non-negative integer s, consisting of n digits." So s could be "0"? Yes, in second test case, s="0". That's allowed, and it has no odd digits, so -1.
But wait, is there any scenario where there are at least two odd digits but the resulting two-digit number might have sum odd? No, sum of two odd digits is even (odd+odd=even). So always even.
Thus, the solution is extremely simple: For each test case, count odd digits. If >=2, output the first odd digit and the last odd digit? But careful: If we output only two digits, we need to ensure that the digits we pick are in order and we skip everything else. So we can output the first odd digit we find and the last odd digit we find (or any two odds). However, is it always possible to take the first odd and the last odd? Yes, because first odd occurs before last odd. That yields a subsequence of length 2. But we need to output the resulting number as a string. So we can simply extract those two characters from the original string in order. But we need to ensure that we don't accidentally include any other digits. The output should be just those two digits. So we can do: find the index of the first odd digit, and the index of the last odd digit (or some second odd). Then print s[index_first] and s[index_last] concatenated.
But note: if the first odd and last odd are the same? That would happen if only one odd. But we only consider >=2, so they are distinct.
One potential nuance: The resulting number must not have leading zeros. Since the first digit is odd, it's fine.
Thus, answer for any string with at least two odd digits is always possible.
Wait, but what about the case where the string is "20"? Digits: 2 (even), 0 (even). No odd digits => -1. "200"? no odd => -1. "10"? digits: 1 (odd), 0 (even). Only one odd => -1? But check: can we form ebne from "10"? Let's see: the number itself "10" is even (ends with 0) so not ebne. Can we delete digits? If we delete '0', we get "1": sum=1 odd, not even. If we delete '1', we get "0": leading zero? Actually "0" is a single digit number, but is it allowed? The problem says "resulting number shouldn't contain leading zeros". Usually "0" is allowed? Let's check: They say "The resulting number shouldn't contain leading zeros." That typically means that the string representation should not start with '0' unless the number is exactly "0"? But they gave example: For second test case "0" they output -1 because impossible, but they didn't say that "0" is considered invalid due to leading zero. However, in the note they said "Answer 013 will not be accepted as it contains leading zeroes." That implies that "0" alone might be allowed? Actually "0" does not have a leading zero; it's just a single zero. Usually in such problems, "0" is allowed as a number without leading zeros. But does "0" satisfy ebne? It is divisible by 2 (even) and sum of digits is 0 which is divisible by 2, so it is even but the number itself is even, so not ebne because number should not be divisible by 2. So "0" is not ebne. So "10" can't produce ebne. So -1 is correct.
Now consider "102": digits: 1 (odd), 0 (even), 2 (even). Only one odd. Can we produce ebne? Could we take "12"? 1+2=3 odd, not even. "10"? sum 1 even? 1+0=1 odd? Actually 1+0=1 odd, not even. "02" not allowed due to leading zero. "102"? ends with 2 even. So no. So -1.
Consider "112": digits: 1,1,2. Two odds (two 1's). Taking first two odds gives "11", sum=2 even, last digit 1 odd -> ebne. So valid.
Thus, the condition seems to be exactly count_odd >= 2.
But wait, there is a subtlety: The resulting number must not contain leading zeros. If the first odd digit we choose is preceded by zeros, that's fine because we skip them. However, what if the first odd digit itself is zero? Impossible because odd digits are 1,3,5,7,9, all non-zero. So fine.
Thus, the solution is straightforward.
But why the problem includes constraints up to 3000 and mentions "delete some digits (they are not necessary consecutive/successive)"? Because some participants might think of more complex construction, but indeed the problem is easy. This is a known Codeforces problem: "Ebony and Ivory"? Actually I recall a problem named "Even But Not Even" from Codeforces Round #616 (Div.2) problem A? Yes, I think it's Codeforces Round #616, Problem A: "Even But Not Even". And the solution is exactly: if there are at least two odd digits, output a number consisting of two odd digits; else -1. So it's that problem.
Let's verify with the sample: For test case 3: 177013, first two odds are at positions 1 and 2: digits "1" and "7" -> "17". That would be acceptable, but they output "17703". That's fine; any answer is accepted. However, check "17": sum=8 even, number 17 odd. So valid. So output "17" would be acceptable. But we must also ensure that we don't accidentally output something like "11"? But first two odds might not be first and second if there are other odds? In 177013, first two odds are 1 and 7. That's "17". That's fine.
But note: Some might argue that if we pick the first odd and the last odd, it could be like "13" for 177013? first odd is 1, last odd is 3 -> "13"? That's also valid. So any two odds works.
Thus the algorithm is:
For each test case:
- Read n, read string s.
- Count odd digits: odd = [d for d in s if int(d)%2==1].
- If len(odd) < 2: print -1.
- Else: find first odd digit index i (first occurrence of an odd digit). Find any second odd digit index j (could be next odd after i, or last odd). Print s[i] + s[j]. Actually we need to output just those two digits. But careful: The subsequence must preserve order. So if we output s[i] and s[j], that's fine. But we must not include any other digits. So we output two characters.
However, the sample output for test case 4 is a long number: 2237344218521717191. This is more than 2 digits. But it's acceptable to output just two odds? Let's check if there is any hidden condition: The problem states: "You can delete some digits (they are not necessary consecutive/successive) to make the given number ebne." It also says: "The resulting number shouldn't contain leading zeros." It doesn't require the resulting number to be of maximum length or anything. So two digits is fine. In Codeforces problem A, many participants output two odd digits indeed. I recall the editorial: "If there are at least two odd digits, we can take two of them to form a solution." So it's correct.
But we need to be careful about the case where the string has exactly two odd digits, but they are not both at positions such that we can take them as a two-digit number? Wait, we can always take them as a two-digit number because we can delete all other digits. The order of digits is preserved, so if we take the first odd and then the second odd (with possibly even digits in between), the resulting number will be the first odd digit followed by the second odd digit. That is a two-digit number. That's fine.
Thus, we can output two odd digits.
But hold on: what about the possibility that the first odd digit is at the very end? If there are at least two odd digits, the first odd cannot be at the very end because there is a later odd. So it's earlier.
Thus, implement:
for each test case: read n (may be ignored) read s (string of length n) odd_positions = [i for i,ch in enumerate(s) if int(ch)%2==1] if len(odd_positions) < 2: print(-1) else: print(s[odd_positions[0]] + s[odd_positions[1]]) // first two odds
Or even first and last: s[odd_positions[0]] + s[odd_positions[-1]] but then might skip some odd between, still only two digits; but if the first and last are far apart, that's also fine.
But we need to ensure we don't accidentally include any other digits. We just output two characters.
One more nuance: The resulting number must be a valid integer without leading zeros. Since the first digit is odd, it's not zero. So fine.
Thus answer is trivial.
However, before finalizing, let's double-check with some edge cases:
Case: s = "2" (n=1, digit even). odd count 0 => -1.
Case: s = "3" (odd count 1) => -1. Because sum=3 odd, not even.
Case: s = "33" (odd count 2) => first odd at index0, second at index1 -> "33", sum=6 even, number 33 odd => ebne.
Case: s = "10" (odd count 1) => -1.
Case: s = "20" (odd count 0) => -1.
Case: s = "1010": odds: 1 and 1 at indices 0 and 2? Actually digits: 1,0,1,0 -> two odds. first two odds: indices 0 and 2 -> number "11" valid.
Case: s = "0"? odd count 0 => -1.
Case: s = "000"? But input says s does not contain leading zeros; that means the first digit cannot be zero. So s can't start with zero. So s won't be all zeros except possibly "0"? "0" is allowed as a single digit zero, but that's the only case with leading zero? Actually "0" has no leading zero because it's the only digit. So okay.
Now, check scenario where there are at least two odd digits, but the first odd digit is part of a leading zero? Can't be because first digit non-zero. So fine.
Thus, solution is straightforward.
But wait, there is an alternative twist: The problem statement says "You can delete some digits (they are not necessary consecutive/successive) to make the given number ebne. You cannot change the order of the digits, that is, after deleting the digits the remaining digits collapse. The resulting number shouldn't contain leading zeros. You can delete any number of digits between 0 (do not delete any digits at all) and n-1." So you must delete digits such that the resulting number is ebne. The resulting number can be of any length >= 1, but if length 1, it cannot satisfy both conditions. So minimal length is 2 (unless there is no solution). Our two-digit solution uses exactly two digits.
Now, is there any case where there are at least two odd digits but you cannot form a two-digit number because the first odd digit is at position i and the second odd digit is at position j>i, but if we take only those two, is it allowed to skip all digits in between? Yes, because we can delete digits arbitrarily. So that's fine.
Thus, implement.
But wait, what about the sample output for test case 4: they output a long number, not just two odds. But as said, any answer is accepted.
Now, confirm with Codeforces problem "Even But Not Even" (Round #616, Div2, Problem A). I recall the solution: Count odd digits; if >=2, print any two odd digits; else print -1. Yes.
But let's double-check the problem statement from memory: Actually the problem "Even But Not Even" might have an additional nuance: They define ebne as number whose sum of digits is divisible by 2, but the number itself is not divisible by 2. And they ask to delete some digits to make it ebne. And the solution is as above. So yes.
One more check: Could there be a scenario with two odd digits but the resulting two-digit number might have sum odd? No, because odd+odd=even. So that's fine.
Thus, we can implement.
Now, regarding output format: For each test case, print answer either -1 or a number.
Implementation:
Read t. For each test case: read n (int) read s (string, length n) odd = [] for i,ch in enumerate(s): if int(ch) % 2 == 1: odd.append(i) if len(odd) >= 2: print(s[odd[0]] + s[odd[1]]) else: print(-1)
But we should consider that the sum of n over all test cases ≤ 3000, so it's fine.
Potential pitfalls: If we output just two digits, does it violate any implicit requirement about the number being non-empty? No.
Double-check test case 1: s="1227", odd indices: 0 (1), 3 (7) => output "1"+"7" = "17". But sample output is "1227". Both acceptable.
Now, test case 3: s="177013", odd indices: 0 (1),1(7),2(7),4(1),5(3). Our output would be "17". Is "17" valid? Let's verify: 1+7=8 even, 17 is odd. Yes. So should be accepted.
Thus answer.
But wait, there is a nuance: The problem statement says "non-negative integer s, consisting of n digits. You can delete some digits (they are not necessary consecutive/successive) to make the given number ebne. ... The resulting number shouldn't contain leading zeros." In some problems, they consider that the resulting number must be a valid integer without leading zeros, but "0" itself is allowed as a representation of zero. However, if we output "17", it's fine.
Thus, final solution.
But I want to be thorough: Could there be a case where there are at least two odd digits but the first odd digit is '0'? No, odd digits are 1,3,5,7,9.
Thus, solution stands.
Now, I recall that in the actual Codeforces problem, some tricky case was when the number has only one odd digit but also many even digits; could we create an ebne by taking more than two digits? For example, s = "2461"? Digits: 2,4,6,1. Odd count = 1. Can we create ebne? The only odd digit is 1. If we take digits: 2,4,6,1: sum=13 odd. If we drop an even digit, sum still odd because dropping even doesn't change parity. So sum always odd. If we drop the odd digit, we get all even digits, but then last digit even, number even. So no. So impossible. s = "22461"? sum=2+2+4+6+1=15 odd; we need even sum. Could we include two copies of odd? Only one odd exists. So can't get even number of odds. So impossible.
But what if we include the odd digit and also include another odd digit? There is none. So impossible.
Thus, exactly one odd digit -> impossible.
Zero odd digits -> impossible because can't get odd last digit.
So condition is both necessary and sufficient: count_odd >= 2.
But is there any scenario where count_odd >= 2 but the resulting two-digit number might have a leading zero? No.
Thus, solution is final.
Now, coding.
Implementation details:
-
We can ignore n, but need to read it to consume input.
-
Use sys.stdin.
Edge Cases: t up to 1000, total n sum ≤ 3000, so it's fine.
Test with given sample:
Input: 4 4 1227 1 0 6 177013 24 222373204424185217171912
Our output: 17 -1 17 ? for last: need to find first two odd digits in that long string. Let's find quickly: s="222373204424185217171912". Let's list digits: 2,2,2,3,7,3,2,0,4,4,2,4,1,8,5,2,1,7,1,7,1,9,1,2? Actually length 24. We need first two odd digits: scanning: first digit 2 even, second 2 even, third 2 even, fourth 3 odd => first odd at index 3 (digit '3'). Next odd? after index 3: index 4 is 7 odd => second odd at index 4 (digit '7'). So our output would be "37"? Actually s[3]='3', s[4]='7' -> "37". But sample output is "2237344218521717191" which is much longer. Both should be acceptable. However, check if "37" is ebne: sum=3+7=10 even, number 37 odd, yes. So valid. So the sample output is just one possible answer.
Thus, our solution would produce "37" for the last test case. But the sample output is different. Since the problem says "If there are multiple answers, you can print any of them.", it's fine.
But we must ensure that in the actual Codeforces problem, the judge accepts any valid answer. So it's okay.
Now, just to be safe, we might output the first two odds. That is definitely correct.
But I've seen some solutions that output the first odd and the last odd, but that also works. However, if the first odd and last odd are the same? That would be if only one odd, but we handle that.
Now, confirm that the input may have leading zeros? It says s does not contain leading zeros. So first digit is non-zero. Good.
Thus, final solution is as above.
But wait, let's double-check the problem statement again: "The resulting number shouldn't contain leading zeros." In some problems, they also require that the resulting number is not empty. So our two-digit number is non-empty.
Thus, code.
Potential issue: There might be a test case where there are exactly two odd digits, but one of them is at the very beginning, but the other is at the end; but if we output just those two, it's fine. However, what if the two odd digits are adjacent? Then our output is two digits, fine.
Thus, solution.
But I recall a twist: In the original problem, they required the resulting number to be not divisible by 2 (i.e., odd) and sum of digits even. Some participants mistakenly thought that if the number has at least two odd digits, you can take the whole number if its last digit is odd and sum even? But that's not always true. But the two-odd solution always works.
Thus, final answer.
I will now produce the final solution in Python.
Implementation:
import sys
def solve(): import sys data = sys.stdin.read().strip().split() if not data: return it = iter(data) t = int(next(it)) out_lines = [] for _ in range(t): n = int(next(it)) # not used but read s = next(it) odd_indices = [] for i, ch in enumerate(s): if (ord(ch) - 48) % 2 == 1: odd_indices.append(i) if len(odd_indices) < 2: out_lines.append("-1") else: # take first two odd digits ans = s[odd_indices[0]] + s[odd_indices[1]] out_lines.append(ans) sys.stdout.write("\n".join(out_lines))
if name == "main": solve()
Edge Cases: ensure that we correctly parse t and each test case.
Test with sample:
Input: 4 4 1227 1 0 6 177013 24 222373204424185217171912
Our output: 17 -1 17 37
Would this be accepted? Probably yes.
But sample output for last is different. As per problem statement, any valid answer is accepted. So it's fine.
Now, let's think: Is there any scenario where our answer "37" for last test case might be considered invalid because it contains leading zero? No.
Thus, final.
Before final, I want to ensure that we didn't miss a case where there are at least two odd digits but the first two odds are both at positions such that the first digit is zero? That can't happen because odd digits are not zero.
One more: Could there be a case where there are two odd digits but after we delete other digits, the resulting number starts with a digit that was originally not the first character? That's fine.
Thus, solution correct.
Now, I can produce final answer.
But maybe there is a scenario where we need to output a number with more than 2 digits because the two-odd number might be "0?" no.
Another nuance: The problem says "You can delete some digits (they are not necessary consecutive/successive) to make the given number ebne." It doesn't restrict that we must keep at least two digits? It says "You can delete any number of digits between 0 (do not delete any digits at all) and n-1." So we must keep at least one digit. We keep two, so okay.
All good.
Thus, final answer.
Now, produce final output. ```python
import sys
def solve() -> None: data = sys.stdin.read().strip().split() if not data: return it = iter(data) t = int(next(it)) out = [] for _ in range(t): n = int(next(it)) # length, not needed further s = next(it) odd_positions = [] for i, ch in enumerate(s): if (ord(ch) - 48) % 2 == 1: # digit is odd odd_positions.append(i) if len(odd_positions) < 2: out.append("-1") else: # take the first two odd digits ans = s[odd_positions[0]] + s[odd_positions[1]] out.append(ans) sys.stdout.write("\n".join(out))
if name == "main": solve()
-