1、笨笨玩糖果

Grade 0 Open Time Saturday, 22 September 2012, 8:45 am
Discount 0.8 Time Discount Saturday, 22 September 2012, 8:45 am
Allow late No Close Time Saturday, 22 September 2012, 8:45 am

  笨笨玩糖果
  【问题描述】
  笨笨和强强正在玩取糖果游戏。他们的游戏规则是这样的:桌上有若干石子,笨笨先取,轮流取,每次必须取质数个。如果某一时刻某一方无法从桌上的糖果中取质数个,比如说剩下O个或1个石子,那么他就输了。笨笨和强强都很聪明,不管哪方存在一个可以必胜的最优策略,他都会按照最优策略保证胜利。于是,笨笨想知道,对于给定的桌面上的糖果数,他究竟能不能取得胜利呢?当笨笨确定会取得胜利时,他会说:“不管强强选择怎样的取糖果策略,我都能保证至多X步以后就能取得胜利。”那么,最小的满足要求的X是多少呢?注意,不管是笨笨取一次糖果还是强强取一次糖果都应该被计算为“一步”。
  【输入格式】
  第一行有一个整数N,表示这个输入文件中包含N个测试数据。
  第二行开始,每行有一个测试数据,其中仅包含一个整数,表示桌面上的糖果数。
  【输出格式】
  你需要对于每个输入文件中的N个测试数据输出相应的N行。如果对于该种情形是笨笨一定取得胜利,那么输出最小的X。否则该行输出-l。
    Sample input
    3
    8
    9
    16
    Sample output
    1
    -1
    3
【数据范围】
输入文件中的数据数N≤10。
每次桌上初始的糖果数都不超过10000。