Got "AADSTS50012: Authentication failed" error for BeginAuth API of Azure IDP

Question

I am trying to do Azure login using Postman without using the MSAL libraries. I have done the authorize and login API's to get the multifactor authentication factors of the user and tried to hit the BeginAuth API by providing the below body. I have enabled per-user MFA authentication for user and enrolled for Microsoft Authenticator app.

{
    "AuthMethodId":"PhoneAppNotification", 
    "Method": "BeginAuth",    "ctx":"",
    "flowToken":""
}

I got Authentication failed response from the server.

{"Success":false,"ResultValue":null,"Message":"AADSTS50012: Authentication failed.","AuthMethodId":"PhoneAppNotification","ErrCode":50012,"Retry":false,"FlowToken":"","Ctx":"","SessionId":null,"CorrelationId":"","Timestamp":"","Entropy":0,"ReselectUIOption":0}

Response from the browser when Push notification works and user logins to Azure portal.

{
    "Success": true,
    "ResultValue": "Success",
    "Message": null,
    "AuthMethodId": "PhoneAppNotification",
    "ErrCode": 0,
    "Retry": false,
    "FlowToken": "",
    "Ctx": "",
    "SessionId": "",
    "CorrelationId": "",
    "Timestamp": "",
    "Entropy": 58,
    "ReselectUIOption": 0
}

I have removed all the sensitive data. Please assume that sensitive data is correct and let me know what is wrong and how to fix the issue. Any help is appreciated.