Most of the answers even the most voted answers didn't do the job properly, they seem to work and the builds work however, a closer look at the file structure and references will show you that not much was done. IntelliJ actually does this whole process automatically.
1) Go to Project Tab and make sure Packages is the active Tab in the drop down like so:
find your com.example package (note test as in com.example.test is not there) right-click and choose Refactor->Rename...
It will issue a warning that multiple directories... (which is actually the desired effect), click on Rename package.
Input the new package name and Refactor...
It will do searches and show you refactoring results.
Click on the Do Refactor button and it will do everything and even rename the folders and files involved... every reference is corrected to this new name.
2) Then Finally change the AndroidManifest.xml file
:)