How to recover lost Microsoft Office 2013 Product Key after Windows 10 Reset PC

Although the Windows Lost Product Key question has been asked before, this is slightly different. I did 'Reset this PC' from Windows 10 Recovery without taking a backup of the system or files. All my files were safe but the Licensed Microsoft Office 2013 was removed. I have unfortunately misplaced the MS Office 2013 Student and Home product box. I have also checked with Windows Helpdesk if any of my emails are associated with the MS Office and the Microsoft Account; sadly, none are.

I read that that the 'Reset' cleans the registry and removes the apps. I am thinking of two ways to try and find the key

1. Use all the Free Key finders around then buy a paid one if they don't work
2. Use Recuva or a similar tool to try and recover the deleted old Windows Registry files

Has anyone faced a similar issue or can you think of an alteate way to try and get the Key? Can you please suggest