Seems I downloaded and installed the wrong C++ Redistributable. Needed to use the x64 one.
It would have been nice if the explanation of what the ARM64, X86 and x64 versions are for that I have linked below had been included in the Common Solutions Post for the issue. There isn't an explanation on the Microsoft page linked in the Common Solutions Post either.
