Ubuntu 18.04.6 LTS on Azure VM can't run apt upgrade: ModuleNotFoundError: No module named 'apt_pkg'

I got this error message when I try to update the software installed with APT:

$ sudo apt update && sudo apt upgrade
Hit:1 http://azure.archive.ubuntu.com/ubuntu bionic InRelease
Get:2 http://azure.archive.ubuntu.com/ubuntu bionic-updates InRelease [88.7 kB]
Get:3 http://azure.archive.ubuntu.com/ubuntu bionic-backports InRelease [83.3 kB]
Get:4 http://security.ubuntu.com/ubuntu bionic-security InRelease [88.7 kB]
Hit:5 http://ppa.launchpad.net/deadsnakes/ppa/ubuntu bionic InRelease
Hit:6 https://packages.microsoft.com/ubuntu/18.04/prod bionic InRelease
Fetched 261 kB in 1s (319 kB/s)
Traceback (most recent call last):
  File "/usr/lib/cnf-update-db", line 8, in <module>
    from CommandNotFound.db.creator import DbCreator
  File "/usr/lib/python3/dist-packages/CommandNotFound/db/creator.py", line 11, in <module>
    import apt_pkg
ModuleNotFoundError: No module named 'apt_pkg'
Reading package lists... Done
E: Problem executing scripts APT::Update::Post-Invoke-Success 'if /usr/bin/test -w /var/lib/command-not-found/ -a -e /usr/lib/cnf-update-db; then /usr/lib/cnf-update-db > /dev/null; fi'
E: Sub-process returned an error code

Something similar happen when I run neofetch:

$ neofetch
Traceback (most recent call last):
  File "/usr/lib/command-not-found", line 28, in <module>
    from CommandNotFound import CommandNotFound
  File "/usr/lib/python3/dist-packages/CommandNotFound/CommandNotFound.py", line 19, in <module>
    from CommandNotFound.db.db import SqliteDatabase
  File "/usr/lib/python3/dist-packages/CommandNotFound/db/db.py", line 5, in <module>
    import apt_pkg
ModuleNotFoundError: No module named 'apt_pkg'

The last important thing I've done is installing python 3.10 which should had gone well. I have no idea what I did wrong.

EDIT: As someone suggested, I already tried running the command apt-get install --reinstall python3-apt but it didn't fixed the problem:

$ sudo apt-get install --reinstall python3-apt
Reading package lists... Done
Building dependency tree
Reading state information... Done
0 upgraded, 0 newly installed, 1 reinstalled, 0 to remove and 0 not upgraded.
Need to get 149 kB of archives.
After this operation, 0 B of additional disk space will be used.
Get:1 http://azure.archive.ubuntu.com/ubuntu bionic-updates/main amd64 python3-apt amd64 1.6.5ubuntu0.7 [149 kB]
Fetched 149 kB in 0s (3207 kB/s)
(Reading database ... 132504 files and directories currently installed.)
Preparing to unpack .../python3-apt_1.6.5ubuntu0.7_amd64.deb ...
Unpacking python3-apt (1.6.5ubuntu0.7) over (1.6.5ubuntu0.7) ...
Setting up python3-apt (1.6.5ubuntu0.7) ...
/usr/lib/python3.10/subprocess.py:955: RuntimeWarning: line buffering (buffering=1) isn't supported in binary mode, the default buffer size will be used
  self.stdin = io.open(p2cwrite, 'wb', bufsize)

Try the answer given in Problem with update-manager: No module named 'apt_pkg' in Ubuntu 13.10, having installed Python 3.4 on /usr/local/lib

sudo apt-get install --reinstall python3-apt