package PokerNim;
use strict;
use warnings;
use Data::Dumper;

sub new {
    my $class = shift;
    my $self = {};

    bless($self, $class);

    $self->{heaps} = shift;

    return $self;
}

sub solve {
    my $self = shift;
    my $nim_sum = undef;

    foreach my $heap (@{$self->{heaps}}) {
        $nim_sum ^= $heap;
    }

    return get_winner_from_nim_sum($nim_sum);
}

sub get_winner_from_nim_sum {
    my $nim_sum = shift;

    return $nim_sum ? 'First': 'Second';
}

1;

use strict;
use warnings;
use Test::More;
use Data::Dumper;

my $TESTING = 0;

use constant {
    MIN_VALUE => 1,
    MAX_VALUE => 100,
    MAX_HEAP_VALUE => 1_000_000_000,
};

run_tests() if ($TESTING);
solve_from_input() if (!$TESTING);

sub run_tests {
    # player who removes the last chip wins the game
    my $pn = new PokerNim([1]);
    is($pn->solve(), 'First');

    $pn = new PokerNim([MAX_HEAP_VALUE]);
    is($pn->solve(), 'First');

    $pn = new PokerNim([1, 1]);
    is($pn->solve(), 'Second');

    # 1 1 1
    # 1 1   First removes 1
    # 1     Second removes 1
    #       First removes 1
    $pn = new PokerNim([1, 1, 1]);
    is($pn->solve(), 'First');

    $pn = new PokerNim([1, 1, 1, 1]);
    is($pn->solve(), 'Second');

    $pn = new PokerNim([1, 1, 1, 1, 1]);
    is($pn->solve(), 'First');

    $pn = new PokerNim([1, 1, 1, 1, 1, 1]);
    is($pn->solve(), 'Second');

    # 2
    # 1   First removes 2
    $pn = new PokerNim([2]);
    is($pn->solve(), 'First');

    # 1 2
    # 1 1   First removes 1
    # 1     Second removes 1
    #       First removes 1
    $pn = new PokerNim([1, 2]);
    is($pn->solve(), 'First');

    # 1 3
    # 1 2   First removes 1
    # 1     Second removes 1
    #       First removes 1
    $pn = new PokerNim([1, 3]);
    is($pn->solve(), 'First');

    # A B C
    # 1 2 2
    # 0 2 2     First removes 1A
    # 0 1 2     Second removes 1B
    # 0 1 1     First removes 1C
    # 0 0 1     Second removes 1B
    # 0 0 0     First removes 1
    $pn = new PokerNim([1, 2, 2]);
    is($pn->solve(), 'First');

    $pn = new PokerNim([2, 1, 3]);
    is($pn->solve(), 'Second');

    # any even number in place of MAX_VALUE is auto-win Second
    my @MAX_BASIC = (1) x MAX_VALUE;
    $pn = new PokerNim(\@MAX_BASIC);
    is($pn->solve(), 'Second');

    my @MAX_MAX = (MAX_HEAP_VALUE) x 1;
    $pn = new PokerNim(\@MAX_MAX);
    is($pn->solve(), 'First');

    done_testing();
}

sub solve_from_input {
    my $game_count = <>;
    chomp($game_count);
    validate_count($game_count);

    foreach (1 .. $game_count) {
        my ($pile_count, $max_pile_interacts) = split(" ", <>);
        validate_count($pile_count);
        validate_count($max_pile_interacts);

        my @heaps = split(" ", <>);
        validate_heaps(\@heaps);

        my $pn = new PokerNim(\@heaps);
        my $winner = $pn->solve();
        print("$winner\n");
    }
}

sub validate_count {
    my $game_count = shift;

    if (!($game_count =~ /^\d+$/)) {
        die "Not a whole number";
    }

    if ($game_count < MIN_VALUE || $game_count > MAX_VALUE) {
        die "Number must be between " . MIN_VALUE . " and " . MAX_VALUE . ", inclusive";
    }
}

sub validate_heaps {
    my $heaps = shift;

    die "Heaps is not an array" if (ref($heaps) ne 'ARRAY');

    if (scalar(@{$heaps}) < MIN_VALUE || scalar(@{$heaps}) > MAX_VALUE) {
        die "Heap count must be between " . MIN_VALUE . " and " . MAX_VALUE . ", inclusive";
    }

    foreach my $heap (@{$heaps}) {
        if ($heap < 1 || $heap > 1_000_000_000) {
            die "Each heap size must be between "
                . MIN_VALUE . " and "
                . MAX_HEAP_VALUE . ", inclusive";
        }
    }
}