让我们定义一个数字 ebne (偶数但不偶数)当且仅当它的数字和可以被 $$$2$$$ 整除,但数字本身不能被 $$$2$$$ 整除。例如,$$$13$$$、$$$1227$$$、$$$185217$$$ 是 ebne 数字,而 $$$12$$$、$$$2$$$、$$$177013$$$、$$$265918$$$ 则不是。如果您仍然不确定 ebne 数字是什么,您可以查看示例注释以获得更多说明。
给你一个非负整数 $$$s$$$,由 $$$n$$$ 数字组成。您可以删除一些数字(它们不一定是连续的/连续的)以使给定的数字 ebne 。您无法更改数字的顺序,即删除数字后剩余的数字会折叠。结果数字不应包含前导零。您可以删除 $$$0$$$(根本不删除任何数字)和 $$$n-1$$$ 之间的任意数量的数字。
例如,如果给定 $$$s=$$$222373204424185217171912 那么使其成为 ebne 的可能方法之一是: 222373204424185217171912 $$$\rightarrow$$$ 2237344218521717191。2237344218521717191的各位数字之和等于$$$70$$$并且能被$$$2$$$整除,但数字本身不能被$$$2$$$整除:这意味着结果是ebne。
找到任何结果为 ebne 的数字。如果无法从给定的号码创建 ebne 号码,请报告该情况。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3000$$$) — 原始数字中的位数。
每个测试用例的第二行包含一个非负整数$$$s$$$,由$$$n$$$ 数字组成。
保证$$$s$$$不包含前导零,并且所有测试用例的$$$n$$$总和不超过$$$3000$$$。
输出
对于输入中给出的每个测试用例,按以下格式打印答案:
- 如果无法创建 ebne 编号,则打印“-1”(不带引号);
- 否则,在删除一些数字(可能是零,但不是全部数字)后打印结果数字。这个数字应该是ebne。如果有多个答案,您可以打印其中任何一个。请注意,不接受带有前导零或空字符串的答案。没有必要最小化或最大化删除的数字数量。
示例
输入 #1
4 4 1227 1 0 6 177013 24 222373204424185217171912
输出 #1
1227 -1 17703 2237344218521717191
注意
在示例的第一个测试用例中,$$$1227$$$已经是一个ebne数(因为$$$1 + 2 + 2 + 7 = 12$$$,$$$12$$$可以被$$$2$$$整除,而同时$$$1227$$$不能被$$$2$$$整除),所以我们不需要删除任何数字。 $$$127$$$ 和 $$$17$$$ 等答案也将被接受。
在示例的第二个测试用例中,显然不可能从给定的数字创建 ebne 数字。
在示例的第三个测试用例中,我们可以通过删除得到很多ebne数字,例如$$$1$$$数字,例如$$$17703$$$、$$$77013$$$或$$$17013$$$。 $$$1701$$$ 或 $$$770$$$ 等答案将不被接受,因为它们不是 ebne 数字。答案 $$$013$$$ 将不被接受,因为它包含前导零。
说明:
- $$$1 + 7 + 7 + 0 + 3 = 18$$$。由于 $$$18$$$ 可以被 $$$2$$$ 整除,而 $$$17703$$$ 不能被 $$$2$$$ 整除,我们可以看到 $$$17703$$$ 是一个 ebne 数。与 $$$77013$$$ 和 $$$17013$$$ 相同;
- $$$1 + 7 + 0 + 1 = 9$$$。因为 $$$9$$$ 不能被 $$$2$$$ 整除,所以 $$$1701$$$ 不是 ebne 数;
- $$$7 + 7 + 0 = 14$$$。这次,$$$14$$$ 可以被 $$$2$$$ 整除,但 $$$770$$$ 也可以被 $$$2$$$ 整除,因此,$$$770$$$ 不是 ebne 数。
在示例的最后一个测试用例中,给出了许多其他可能的答案之一。另一个可能的答案是: 222373204424185217171912 $$$\rightarrow$$$ 22237320442418521717191 (删除最后一位数字)。