Rewriting Custom post type

I have all my posts in this format /gallery/%postname%, where ‘gallery’ is my custom post type, but i want to change it to /media/gallery/%postname%, and make sure that all my current posts still get me to the same page as they did before without a Not Found error.

I tried 'rewrite' => array("slug" => "/media/gallery"),

but all the posts lead me to Not Found page.

Help please 🙂