JDCC '15 Contest 3 P2 - Splitting Presents

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type

On Christmas morning, Matthew and Emily rush down the stairs excited to open their presents. They find N presents, one of which is the biggest present they've ever seen! After examining the presents, they find that the presents don't specify their recipients, which causes them to start fighting over who gets the big present. In order to stop the kids' fighting, their parents devise a way for the kids to split the presents.

They split the presents as follows: Emily goes first and takes up to M presents for herself. Then Matthew takes up to M presents for himself. The two kids alternate taking up to M presents, however they aren't allowed to take the big present until all the other presents have been distributed. Furthermore, during each child's turn, they must take at least one present.

Both Matthew and Emily don't care about any of the small presents — they only want the big present. If they split the presents optimally, which child is guaranteed to receive the big present?

Input Specification

The first line of input provides the number of test cases, T (1 \le T \le 100). T test cases follow. Each test case consists of one line containing integers N, M (1 \le N, M \le 1 000).

Output Specification

For each test case, your program should output either Emily or Matthew, the name of the child who will get the big present.

Sample Input

5 3
12 3
14 5

Sample Output


Explanation for Sample

In the first test case, Emily can take one present on her turn, leaving 4 presents in total. Then, whether Matthew takes 1, 2, or 3 presents, Emily can take 3, 2, or 1 presents respectively on the turn after, guaranteeing her the big present.


There are no comments at the moment.