Палиндром по счёту

Выпишем по возрастанию все числа, которые читаются одинаково в обе стороны в десятичной записи: 1, 2, …, 9, 11, 22, … Какое из них стоит на месте $k$?

Одно целое число $k$ от $1$ до $10^9$.

Одно число.

Палиндромов данной длины ровно столько, сколько вариантов первой половины. Отсчитайте нужную длину, а потом соберите палиндром из номера половины.