Under construction

Still being built. Things may change

Odd and Even Game

Interview

Time limit1sMemory limit1024 MB

Summary
Two players alternately take cards, and after each player's first card, every card they take must share its parity. Determine the winner under optimal play.
Level

Medium5 of 10

Topics
Game theory, Dynamic programming
Solved
No attempts yet

Problem

NN cards are laid out in a row on the floor from left to right. The card at position ii from the left has the integer AiA_i written on its front face.

Chaewan plays an odd-even card game with Heeda. The rules are as follows.

  1. The two players take turns, and Chaewan goes first.

  2. On each turn, a player picks one card from the cards remaining on the floor and takes it. A player may only take a card that satisfies the following condition.

    • There is no restriction on the first card a player takes.
    • Every card a player takes after the first must have the same parity as the first card that player took.
  3. A player who cannot take any card on their turn loses.

Assuming both players play optimally, determine the winner of the game.

Input

The first line contains the number of test cases TT. (1≤T≤100)(1 \le T \le 100)

Each test case follows on the next lines. A test case consists of two lines. The first line contains the number of cards NN. (1≤N≤100)(1 \le N \le 100)

The second line contains the integers A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N written on each card, separated by spaces. (1≤Ai≤100)(1 \le A_i \le 100)

Output

For each test case, print one line. Print amsminn if Chaewan wins, and heeda0528 if Heeda wins.

Examples1

  1. Example 1

    Input
    3
    4
    1 2 3 4
    6
    1 2 3 4 5 6
    5
    1 2 1 3 2
    
    Expected output
    heeda0528
    heeda0528
    amsminn