We optimize two-mode, entangled, number states of light in the presence of loss in order to maximize the extraction of the available phase information in an interferometer. Our approach optimizes over the entire available input Hilbert space with no constraints, other than fixed total initial photon number. We optimize to maximize the Fisher information, which is equivalent to minimizing the phase uncertainty. We find that in the limit of zero loss the optimal state is the so-called N00N state, for small loss, the optimal state gradually deviates from the N00N state, and in the limit of large loss the optimal state converges to a generalized two-mode coherent state, with a finite total number of photons. The results provide a general protocol for optimizing the performance of a quantum optical interferometer in the presence of photon loss, with applications to quantum imaging, metrology, sensing, and information processing. Comment: 3 figures