How to count rows with two values in any of the many columns in Excel?

Say I have some Excel columns that look like this:

    A       B       C       D
1   Amy     Bob     Carol   David
2   Carol   David   David   Carol
3   Bob     Carol   Amy     Amy
4   David   Amy     David   Amy

I need to count the number of rows where both Amy and Bob occur, no matter which column they are in. In this example, the number should be 2 (row 1 and row 3).

I already know COUNTIFS with which I can count the number of rows with 'Amy' in column A (or any particular column), and 'Bob' in column B (or any particular column). The formula would be:

=COUNTIFS(A1:A4,"Amy",B1:B4,"Bob")

However, this formula seems to require you to specify the columns. I tried to change it to

=COUNTIFS(A1:B4,"Amy",A1:B4,"Bob")

and it retued 0, which is not what I'm after. I need to count the number of rows where both Amy and Bob occur, regardless of the columns they are in. How can I achieve this? Thanks!