add base slug for post_tag for posts and custom posts

I need help trying to add post_tag taxonomy for a custom post type. The website I am working at, uses Posts for News (there is no blog). Then there is a Gallery custom post that also uses the post_tag. Currently, the tag for news is like the following: /tag/my-tag-name. I want this tag to be the following way:

/news/tag/my-tag-name
/gallery/tag/my-tag-name

I was able to add the /news/tag/my-tag-name through the the "Tag Base" in the "Permalinks Settings." But I can't get it to work with gallery/tag/my-tag-name. It keeps saying "Page not found" Can you give me the procedure behind achieving what I want. Also I want to mention this. I don't necessarily care to have news slugs based on category; /year/month/day/post-name is fine with me.