For the following questions, assume there is no padding.

With a block cipher having a 128 bit key and a 64 bit block length to MAC a 512 bit message, how many evaluations of the block cipher must be performed in order to calculate the tag? Please explain.

If the key size were reduced to 64 bits, how would the answer change? Please explain.