Mac-sforge motivation for storing pairs I don't understand why Q keeping pairs of  instead of m like mac-forge solves the problem of generating a new tag on a previously authenticated message. Say, a previously authenticated message for "Cat" is tag 90, Adversary can retrieve (Cat, 90) from the query. However, if Adversary is able to successfully forge a new tag (Cat, 138), I almost feel as if sforge weakens the definition. Q has Cat, but it doesn't have 138 as the tag, so this will pass mac-sforge, but not pass mac-forge. Could someone clarify my confusion?

Relevant passage From Katz and Lindell:

"As defined, a secure MAC ensures that an adversary cannot generate a valid tag on a new message that was never previously authenticated. But it does not rule out the possibility that an attacker might be able to generate a new tag on a previously authenticated message. That is, a MAC guarantees that if an attacker learns tags t1, . . . on messages m1, . . ., then it will not be able to forge a valid tag t on any message m ̸∈ {m1, . . .}. However, it may be possible for an adversary to ”forge” a different valid tag t′1 ̸= t1 on the message m1. In general, this type of adversarial behavior is not a concern. Nevertheless, in some settings it is useful to consider a stronger definition of security for MACs where such behavior is ruled out.

Formally, we consider a modified experiment Mac-sforge that is defined in exactly the same way as Mac-forge, except that now the set Q contains pairs of oracle queries and their associated responses. (That is, (m, t) ∈ Q if A queried Mack(m) and received in response the tag t.) The adversary A succeeds (and experiment Mac-sforge evaluates to 1) if and only if A outputs (m,t) such that Vrfyk(m, t) = 1 and (m, t) ∈/ Q.

DEFINITION 4.3 A message authentication code Π = (Gen,Mac,Vrfy) is strongly secure, or a strong MAC, if for all probabilistic polynomial-time adversaries A, there is a negligible function negl such that:
Pr[Mac-sforgeA,Π(n) = 1] ≤ negl(n)."
A security definition is stronger if we make it easier for the attacker to win. The point being that the stronger definition rules out even this easier way of winning

In the specific case noted in the question, you are indeed correct.
The scenario you describe is the following:

An attacker queries "Cat" and receives the tag "90". It then computes the tag "138" such that $\mathsf{Vrfy}_k(\text{Cat},138)=1$ and outputs the pair $(\text{Cat},138)$.

The regular $\mathsf{MAC\text{-}forge}$ experiment will reject this output. I.e., the attacker does not win, and therefore this security definition does not rule out the existence of said attacker.

The stronger $\mathsf{MAC\text{-}sforge}$ experiment will accept this output. I.e., the attacker wins, and therefore this security definition rules out the existence of said attacker.