\(N=1\) の場合答えは \(0\) です．以下， \(N \geq 2\) とします．

非負整数 \(x\) に対し，\(\mathrm{count}(x)\) を \(x\) 未満 の回文数の個数とします．

\(\mathrm{count}(K) \lt N\) を満たす最大の非負整数 \(K\) が，この問題で出力すべき答えとなります． \(\mathrm{count(x)}\) は広義単調増加であるため， \(\mathrm{count}(x) \lt N\) を満たすかどうかで\(x\) を二分探索することでこの問題を解くことができます．

次に，\(\mathrm{count}(x)\) を求める方法を考えます．回文数としてありうるのは次の3通りです．正整数 \(X\) に対して，\(\mathrm{str}(X)\) を \(X\) を文字列としてみなしたもの，\(\mathrm{rev}(X)\) を \(X\) を文字列としてみなし，それを前後反転させたものとします．

1. 一桁の非負整数
2. \(\mathrm{str}(X)\), \(\mathrm{rev}(X)\) をこの順につなげたもの
3. \(\mathrm{str}(X)\), 一桁の非負整数 \(\mathrm{rev}(X)\) をこの順につなげたもの

それぞれについて個数を数えます．1. については \(10\) 個しか候補がないので愚直に判定できます．

2.の場合を考えます．\(X\) としてありうるものがいくつあるかを数えることにします．\(X\) が大きくなればなるほどできる回文数も大きくなることから，\(X\) で二分探索をして \(X\) としてありうるものの個数を数えることができます．

3.についても2.と同様にできます．間に挟まる一桁の非負整数 \(10\) 通りそれぞれについて二分探索で個数を数えて足せばよいです．

\(K\) を求める（初めに説明した）二分探索の範囲は，サンプルからもわかる通り \(1\) 以上 \(90000000000000000000000000000000009 \) 以下に対して行う必要があります．これは 64bit 整数に収まらない範囲であるため，多倍長整数を用いる必要があります．計算量は \(\log N\) に対する多項式時間で収まり，十分高速に動作します．