Captain Andrei:
Hurry to the Varka Silenos Barracks and help Giant's Minion Hansen there.
To get there quickly, use the Scroll of Escape: Varka Silenos Barracks I gave you. You could also ask a Gatekeeper for help.