Cant log into work account, I am admin and updated password, now stuck in authenticator loop

Question

I am an administrator for my business and got a new phone. The authenticator app was on my old phone which was water damaged and could not be used. When I tried downloading the new authenticator app, it gives me the option to Approve a request on my authenticator app, or to enter a passcode, which I assume would need to be from the authenticator app. How can I approve it or enter the passcode if I can't log in to get it? And it sent me to update my password which now means that I can't log into any of my devices, because they all want the authenticator app, so I am in this loop of needing to use the app to approve the log in anywhere. I am the admin, so I can't log into the background Office 365 platform to change anything and am completely locked out of my cloud for my business. Please help!! And thanks so much in advance!!