Highlight Rows When Change In Condition Occurs

I have a whole spreadsheet of data which looks confusing so I need to make it look more attractive to the viewer.

I have column A which shows a number of the branch conducting the transaction and the column will contain numerous different branches which I have sorted into branch order.I think there are too many branches to use the conditional formatting condition (probably 5000 different numbers)

What I wish to do is change the colour of the cell when the branch name changes.

For example
Column A= Branch number
123
123
123
345
345
345
456
456
456
789
789

What I need is to highlight all branches 123 with a colour (any colour say red) but when the change in branch number occurs to 345 use a different colour to highlight all the branches (cells) with the number 345 (say grey).Then when the branch changes to 456 use the same colour that highlighted branch 123 (ie red) .Then again when the branch changes to 789 change the colour back to grey again so the spreadsheet shows rows highlighted when a different branch occurs

The above example would look like
Column A
all branches with 123 ( cell highlighted any colour but say red)
branches 345 cells highlighted grey
branches 456 cells highlighted red
branches 789 grey