I cannot set up my Two way authentication anymore (Windows Phone)

Hello,

I've come across a problem with 2FA on my Windows Phone after I reseted my Windows OS on it. Since then, when I try to set it up again (tried to use: Microsoft Authentificator and Authentification for Windows apps), it would say the code is incorrect. Everything goes well when I set it up, but after I receive my Recovery Key and it asks me to input the code from my authentificator it always says its incorrect, and I tried that multiple times. 

Things that I tried are:
1. Reinstalling Microsoft Authentificator
2. Un-assingning my Teamviewer account from Teamviewer 13 Desktop app
3. Using the Secret code instead of the QR Scan code to set it up 
Neither of them worked. Can you suggest a fix ?