Поврежденный пароль 2

После долгих лет поисков, Алексей наконец-то нашёл на свалке свою флешку с паролем от криптокошелька. К сожалению данные оказались повреждены, и пароль удалось восстановить не полностью.

Символы, которые не поддались восстановлению, обозначены как «?».

К счастью, Алексей помнит, что для пароля выполнялись следующие условия:

• в пароле использовались только десятичные цифры (0 – 9).
• нет двух одинаковых соседних цифр.
• это число является палиндромом.
• левая половина числа (длина числа, нацело деленная на 2) также является палиндромом.
• пароль не может начинаться на цифру 0, является натуральным числом.

Также Алексей помнит, что писал программу для генерации пароля, которая выводила по возрастанию все числа, которые удовлетворяют вышеописанным условиям, и он выбрал K-е число. Помогите Алексею определить это K-ое число, либо вывести «-1», если он ошибся.

Входные данные

Входной файл INPUT.TXT содержит в первой строке натуральное число Q – количество наборов входных данных. В каждом наборе по 2 строки: в первой натуральное число K, во второй – строку длиной от 1 до 10 000, состоящую только из цифр (0 – 9) и вопросительных знаков («?»).

Ограничения: 1 ≤ K ≤ 10¹⁸; 1 ≤ Q ≤ 1000.

Выходные данные

В выходной файл OUTPUT.TXT на каждый тестовый набор выведите ответ в отдельной строке – K-й пароль.

Пример

Автор задачи

Владимир Игоревич Лукьянчиков

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]