OR...................
if any of your characters have the Palidor Esper, then keep scanning MagiMaster from time to time and when he has HP low enough for at 3 of ur party members to attack him, he will cast ultima while your 1st person's in the air and wont die.
OTHERWISE............you're screwed, so start from phoenix cave.

I AM THE ULTIMATE FF3, FF7, CT, AND CC MASTER!!!!!!!