Remove custom post type slug from URL and add taxonomy Slug

I am having an issue while changing a custom post type URL. Current post type URL is:

http://example.com/product/product-slug

where product is a custom post type.

I want to change it to:

http://domain.com/brand/brand-slug/product-slug

where brand is the custom taxonomy.

I found code that removes /product/ from the custom post type URL and it’s working fine for me. I am using following code.

function gp_remove_cpt_slug( $post_link, $post, $leavename ) {

    if ( 'product' != $post->post_type || 'publish' != $post->post_status ) {
        return $post_link;
    }

    $post_link = str_replace( '/' . $post->post_type . '/', '/', $post_link );

    return $post_link;
}
add_filter( 'post_type_link', 'gp_remove_cpt_slug', 10, 3 );


function gp_parse_request_trick( $query ) {

    // Only noop the main query
    if ( ! $query->is_main_query() )
        return;

    // Only noop our very specific rewrite rule match
    if ( 2 != count( $query->query ) || ! isset( $query->query['page'] ) ) {
        return;
    }

    // 'name' will be set if post permalinks are just post_name, otherwise the page rule will match
    if ( ! empty( $query->query['name'] ) ) {
        $query->set( 'post_type', array( 'post', 'page', 'product' ) );
    }
}
add_action( 'pre_get_posts', 'gp_parse_request_trick' );

Permalink setting is /%postname%/. But when I am changing the permalink setting to /brand/%brand%/%postname%/, all the custom post types start giving me 404 error.

Please suggest what changes need to be done in the above code to make it work.