Handy wechsel, Authenticator keine Cloud sicherung, kein zugriff auf altes Handy

Habe mein Handy gewechselt und wollte heute nach langem wieder die Authenticator App nutzen und musste feststellen das sie nicht funktioniert. wenn ich mich in der App anmelde mit Microsoft Konto möchte die App das ich auf meinem mobilen gerät schaue und den Code eingeben soll der dort generiert wurde, aber dies funktioniert ja nicht, da ich ja gerade das mobile gerät anmelden möchte was ich jetzt nur noch habe..... Was soll ich tun.....