If \(N\) is a \(2\)-digit number, the problem is easy. Below, we assume that \(N\) is a \(k\)-digit \((3 \leq k)\) number.

\(10^{k-1}-1=999...999\) is a \((k-1)\)-digit number, which is periodic. Thus, other than this, we only need to check \(k\)-digit numbers to find the greatest periodic number at most \(N\).

Consider a \(k\)-digit periodic number \(n\) that is the concatenation of \(\frac{k}{a}\) copies of an \(a\)-digit positive number \(m\). Let \(N'\) be the topmost \(a\) digits of \(N\) interpreted as an integer. Then, we only need to consider \(m=N'-1\) and \(N'\), because we always have \(n \leq N\) for \(a=N'-1\) and \(N < n\) for \(a=N'+1\).

Now we only have to consider \(O(\log {N})\) periodic numbers, enabling us to solve the problem in \(O(\log^2 N)\) time per test case.

Beware the case \(N'\) is a power of \(10\), or there is no \(k\)-digit periodic number at most \(N\).