[math-fun] squares beginning with n

Given n, A018851 and A018796 give the smallest square that begins with n Question: does such a square always exist, and if so how big can the smallest example be?