You can do this all on the gateway.

You can create different incoming dial peers, that look like this:

dial-p v 1 voip

answer-address 1001

translation-profile (adds a 955 to beginning of called number)

dial-p v 2 voip

answer-address 1002

translation-profile (adds a 966 to beginning of called number)

dial-p v 3 pots

port 0/0/0

destination-pattern 955.T

dial-p v 4 pots

port 0/0/1

destination-pattern 966.T

That would do it. Alternatively, you could add the prefixes in CUCM by creating different route patterns with different partitions and adding different digits there.

-nick