Microsoft authenticator loop, colleague cannot use the app because we need the app to login, but we cant because we're installing the app.

Question

We had to use microsoft's Authenticator app from work for an extra step for protection. We had this on our work cell phone that we had to replace because it was out of date. We set this cell phone to factory settings and handed it over to our boss. Now we have a new cell phone, but when we download the authenticator app they ask for the code to enter on the authenticator app so we can use this app? We are actually in a loop of actions we can take. (we did not make a backup). Now my colleague cannot access sharepoint and soon will not be able to access her emails. What should we do now? Our colleagues at headquarters can't really help us here either. Thanks in advance!