Git not recognizing remote branches?

Question

I'm a little new to git/github and I'm having an issue with pushing my changes to a new branch. Here's some relevant context before I get into it:

Remote Branches

• main
• test_deploy

Inputs/Outputs

git status: On branch test_deploy nothing to commit, working tree clean

git branch -vv:

master      e6c262d find out why case switch doesnt work
* test_deploy e6c262d find out why case switch doesnt work

git branch -r:

origin/main
origin/test_deploy

Problem

After committing changes, I try to push with git push origin test_deploy but I'm met with:

 ! [rejected]        test_deploy -> test_deploy (non-fast-forward)
error: failed to push some refs to 'https://github.com/user/project_API.git'
hint: Updates were rejected because the tip of your current branch is behind
hint: its remote counterpart. Integrate the remote changes (e.g.
hint: 'git pull ...') before pushing again.
hint: See the 'Note about fast-forwards' in 'git push --help' for details.

What I've tried

1. git pull which outputs There is no tracking information for the current branch. Please specify which branch you want to merge with.

2. git pull test_deploy which outputs

   fatal: Could not read from remote repository.
   
   Please make sure you have the correct access rights
   and the repository exists.
   
   

3. git merge test_deploy which outputs Already up to date.

4. git rebase test_deploy which outputs Current branch test_deploy is up to date.

5. Deleting github credits manager and reinstalling it

6. git reset -hard which didnt seem to solve anything

7. Deleting the .git folder and reinitializing the remote

Conclusion

I feel like a chimp in a space shuttle because I don't know what buttons to press anymore. If someone could give me pointers as to whats happening and why I can't push, I'd appreciate it.