I would start with two digit numbers...
100 factors 2,5,25,4,50,10, 100, 1 eight factors check that.
81 factors 3,9,27,81,1six factors
64 2,4,16,32, 64,1,8 seven factors
recheck those, and work downward to find one with nine factors.
There aren't that many two-digit perfect squares. I'd simply try them all out, starting with the largest I can think of (since that's most likely to have nine factors) and work backwards until I find one that works.