How can I create a regex that parses all lines of a string for a substring, and returns a match only if the substring is not found?

How can I create a regex that parses all lines of a string for a
substring, and returns a match only if the substring is not found?

I am trying to build a regular expression but am finding it difficult to
do so for this one particular case. I want to return a match only if the
string I am trying to parse does not contain a specific substring. For
example (searching for the substring "test" with case insensitivity):
"Line one
Line two
Line test three" - Return false.
"Line test one" - Return false.
"Tfest" - Return true.
"Tfest
Tdhf
Line three" - Return true.
I've been able to do this for single line strings using ^((?!message
1).)*$ but I'm not sure about multi-line strings.
PS: I don't want to start a debate on using string operations VS regular
expressions. Performance is a concern. The constraint of the question is
that the solution must use regular expressions.