2005 Pascal Problem 24

A positive integer is called a *perfect power* if it can be written in the form a^b, where a and b are positive integers with b \ge 2. For example, 32 and 125 are perfect powers because 32 = 2^5 and 125 = 5^3.

The increasing sequence 2, 3, 5, 6, 7, 10, \ldots consists of all positive integers which are not perfect powers. The sum of the squares of the digits of the 1000th number in this sequence is

\textbf{(A)}\ 42\quad \textbf{(B)}\ 26\quad \textbf{(C)}\ 33\quad \textbf{(D)}\ 18\quad \textbf{(E)}\ 21

If there are no answer choices shown, enter a numerical answer.

Full credit to this problem is given to the CEMC, you may view all Pascal contests here.