Solution:

Each pair of consecutive digits must be one of the two-digit squares $16,$ $25,$ $36,$ $49,$ $64,$ $81.$ So each digit determines its successor uniquely if one exists: $1 \to 6,$ $2 \to 5,$ $3 \to 6,$ $4 \to 9,$ $6 \to 4,$ $8 \to 1,$ while $5$ and $9$ end the number.

Following these chains from each possible starting digit, the longest strings are $25,$ $3649,$ and $81649.$ The five-digit chain $8 \to 1 \to 6 \to 4 \to 9$ beats everything else, so $N = 81649,$ whose leftmost three digits are $816.$