1999 Pascal Problem 24

A number is formed using the digits 1, 2, ..., 9. Any digit can be used more than once, but adjacent digits cannot be the same. Once a pair of adjacent digits has occurred, that pair, in that order, cannot be used again. How many digits are in the largest such number?

\textbf{(A)}\ 72\quad \textbf{(B)}\ 73\quad \textbf{(C)}\ 144\quad \textbf{(D)}\ 145\quad \textbf{(E)}\ 91

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.