Stone Game

  Cdfpysw and Nanaya love to play some games together. Today, they find a new stone game.
  There are N piles of stones on the table, there are a_i stones in the i_th pile.
  They will play in turns. In each turn, one player should take out some stones in one pile. If stones he takes is k, all stones before he takes in that pile is p. It should be satisfied that k > 0 and gcd(k, p) = 1. gcd(a, b) means the greatest common divisor of a and b.
  Cdfpysw will take the first turn, and the first one who cannot take stones is the loser.
  If they will both use the best strategy for win, can you predict who will be the winner?

  The first line is an integer T, means the number of cases.
  For each case:
    The first line is an integer N, means the number of piles.
    The next line contains N integers a_1, a_2, ..., a_N, means the number of stones in each pile.
  T <= 50
  N <= 10⁶
  0 <= a_i <= 10⁶

  In each case, you should output "Case #%d: " first.
  Then you should print the winner's name, "Cdfpysw" or "Nanaya".

3
2
2 4
2
1 3
3
1 3 5

Case #1: Nanaya
Case #2: Cdfpysw
Case #3: Nanaya

校第十五届大学生程序设计竞赛暨2015省赛集训队选拔赛