I played this great game a long time ago.... i remember that someone told me to visit all the beaches in the world, then return to him and he would give me something.

I think it was a kind of chocobo king (not sure), can someone tell me what means Visit all beaches, i mean how to do that? just walk on them?? and what i get if i do it? Thanks for your help.