// hráč může vzít jen takový počet mincí, které jsou mocninou 2
// např.: pokud si hráč vezme 100 mincí,

const
  fs = require("fs");

const piles = [
  1,
  2,
  3,
  4,
  5,
  6,
  7,
  8,
  9,
  10,
  11,
  12,
  13,
  14,
  15,
  16,
  17,
  18,
  19,
  20,
  3197,
  2103,
  1705,
  3237,
  1182,
  5385,
  1099,
  6539,
  8841,
  230,
  3211,
  9408,
  4457,
  8340,
  9303,
  4567,
  2288,
  8002,
  3960,
  5891,
  6502,
  2397,
  5335,
  8515,
  3920,
  6892,
  3189,
  3920,
  7997,
  517,
  2210,
  4330,
  3692,
  1477,
  6961,
  502,
  5076,
  507,
  7405,
  1435,
  522,
  9165,
  8931,
  210,
  2816,
  6182,
  345,
  1385,
  2210,
  7577,
  2393,
  9813,
  7564,
  8585,
  6652,
  7862,
  350,
  3447,
  8929,
  3815,
  2810,
  683,
  5239,
  5646,
  5579,
  9437,
  1812,
  600,
  1132,
  3061,
  6539,
  5889,
  1256,
  6515,
  7377,
  4199,
  7289,
  2278,
  425,
  8537,
  3230,
  4512,
  2246,
  2262,
  9277,
  9349,
  949,
  9682,
  8000,
  5308,
  718,
  3302,
  923,
  6898,
  8983,
  386,
  3400,
  3189,
  4805,
  204
];

const players = [
  "Pat", // begins each game
  "Mat"
];


const largestSquare = n => {
  let i = 0;
  while ((i + 1) * (i + 1) <= n) {
    ++i;
  }
  return i * i;
}

const gameLoop = pile => {
  let turn = 0;

  while (pile > 0) {

    let taken;
    let remaining;
    let suggested = pile;

    while (suggested >= 1) {
      taken = largestSquare(suggested);
      remaining = pile - taken;
      if (remaining !== 0 && Number.isInteger(Math.sqrt(remaining))) {
        suggested = taken - 1;
      } else {
        break;
      }
    }

    pile -= taken;

    // win strategy
    // after player takes some coins
    // remaining number of coins should be 0 or not equal to square root

    console.log(`${players[turn]} took ${taken}`);

    turn ^= 1; // change turn
  }

  turn ^= 1

  console.log(`${players[turn]} empties pile`);

  return players[turn];

};

// console.log("Winner: " + gameLoop(30));

fs.writeFile("output", JSON.stringify(piles.map(gameLoop)));