Take Blinky and visit that guy that fell in love with a statue. Then ask him for help in exchange.

Your Majesty, yes, I have no identity documents on me, but that's because I was a statue mere fifteen minutes ago.