Did you already try the "I lost my authenticator and I want to remove it from my account" button? If you can't find your phone that's the only option you have. If you call or write the support they will just tell you to go to the website and use that button. I never tried to remove my authenticator so I don't know which informations they want but that's your only option. I don't know if they look at the country because you know you could just moved from Canada to US and back or so.