use strict;
use warnings;

while (<DATA>) {
    print "Match $_" if /58=Invalid(?:(?!59=3).)*$/;
}

__DATA__
58=Invalid Contract;59=3;45=Test;23=Test12
58=Invalid Contract;45=Test