 static short duplex[][3]={
     0, -2,  9,    1, -7,-21,    0,  7, 21,    1,  7,-21,    0, -7, 18,
     1,  6,-18,    0,-11,  6,    1,  9,  0,    0,-13, -6,    1,  6,  0,
     0,  6,  0,    1,  6,  0,    0,-11, 12,
 
     0, -7,  9,    1,  0,-21,    0,  1, 21,    1,  0,-21,    0, -4, 21,
     1, 12,  0,    1,  3, -1,    1,  1, -1,    1,  1, -2,    1,  0, -2,
     1, -1, -2,    1, -1, -1,    1, -3, -1,    0,  0, 10,    1,  2, -1,
     1,  1, -1,    1,  1, -2,    1,  0, -2,    1, -1, -2,    1, -1, -1,
     1, -2, -1,    0, -8,  0,    1,  8,  0,    1,  3, -1,    1,  1, -1,
     1,  1, -2,    1,  0, -3,    1, -1, -2,    1, -1, -1,    1, -3, -1,
     1,-12,  0,    0, 12, 11,    1,  2, -1,    1,  1, -1,    1,  1, -2,
     1,  0, -3,    1, -1, -2,    1, -1, -1,    1, -2, -1,    0, -4, 12,
 
     0,  5,  6,    1,  1, -3,    1,  0,  6,    1, -1, -3,    1, -2,  2,
     1, -3,  1,    1, -2,  0,    1, -3, -1,    1, -2, -2,    1, -1, -2,
     1, -1, -3,    1,  0, -5,    1,  1, -3,    1,  1, -2,    1,  2, -2,
     1,  3, -1,    1,  2,  0,    1,  3,  1,    1,  2,  2,    1,  1,  2,
     0, -8, 16,    1, -2, -1,    1, -2, -2,    1, -1, -2,    1, -1, -3,
     1,  0, -5,    1,  1, -3,    1,  1, -2,    1,  2, -2,    1,  2, -1,
     0, -1, 12,
 
     0, -7,  9,    1,  0,-21,    0,  1, 21,    1,  0,-21,    0, -4, 21,
     1, 10,  0,    1,  3, -1,    1,  2, -2,    1,  1, -2,    1,  1, -3,
     1,  0, -5,    1, -1, -3,    1, -1, -2,    1, -2, -2,    1, -3, -1,
     1,-10,  0,    0, 10, 21,    1,  2, -1,    1,  2, -2,    1,  1, -2,
     1,  1, -3,    1,  0, -5,    1, -1, -3,    1, -1, -2,    1, -2, -2,
     1, -2, -1,    0, -2, 12,
 
     0, -7,  9,    1,  0,-21,    0,  1, 21,    1,  0,-21,    0,  6, 15,
     1,  0, -8,    0,-10, 14,    1, 16,  0,    1,  0, -6,    1, -1,  6,
     0,-11,-10,    1,  6,  0,    0,-10,-11,    1, 16,  0,    1,  0,  6,
     1, -1, -6,    0, -8, 12,
 
     0, -7,  9,    1,  0,-21,    0,  1, 21,    1,  0,-21,    0,  6, 15,
     1,  0, -8,    0,-10, 14,    1, 16,  0,    1,  0, -6,    1, -1,  6,
     0,-11,-10,    1,  6,  0,    0,-10,-11,    1,  7,  0,    0, -1, 12,
 
     0,  5,  6,    1,  1, -3,    1,  0,  6,    1, -1, -3,    1, -2,  2,
     1, -3,  1,    1, -2,  0,    1, -3, -1,    1, -2, -2,    1, -1, -2,
     1, -1, -3,    1,  0, -5,    1,  1, -3,    1,  1, -2,    1,  2, -2,
     1,  3, -1,    1,  2,  0,    1,  3,  1,    1,  2,  2,    0, -7, 18,
     1, -2, -1,    1, -2, -2,    1, -1, -2,    1, -1, -3,    1,  0, -5,
     1,  1, -3,    1,  1, -2,    1,  2, -2,    1,  2, -1,    0,  7,  8,
     1,  0, -8,    0,  1,  8,    1,  0, -8,    0, -4,  8,    1,  7,  0,
     0,-10,  4,
 
     0, -7,  9,    1,  0,-21,    0,  1, 21,    1,  0,-21,    0, 12, 21,
     1,  0,-21,    0,  1, 21,    1,  0,-21,    0,-17, 21,    1,  7,  0,
     0,  6,  0,    1,  7,  0,    0,-16,-10,    1, 12,  0,    0,-16,-11,
     1,  7,  0,    0,  6,  0,    1,  7,  0,    0,-10, 12,
 
     0, -7,  9,    1,  0,-21,    0,  1, 21,    1,  0,-21,    0, -4, 21,
     1,  7,  0,    0, -7,-21,    1,  7,  0,    0,-10, 12,
 
     0, -2,  9,    1,  0,-17,    1, -1, -3,    1, -2, -1,    1, -2,  0,
     1, -2,  1,    1, -1,  2,    1,  0,  2,    1,  1,  1,    1,  1, -1,
     1, -1, -1,    0,  6, 17,    1,  0,-17,    1, -1, -3,    1, -1, -1,
     0, -1, 21,    1,  7,  0,    0,-10, -9,
 
     0, -7,  9,    1,  0,-21,    0,  1, 21,    1,  0,-21,    0, 13, 21,
     1,-13,-13,    0,  5,  4,    1,  8,-12,    0, -9, 12,    1,  8,-12,
     0,-16, 21,    1,  7,  0,    0,  6,  0,    1,  6,  0,    0,-19,-21,
     1,  7,  0,    0,  6,  0,    1,  6,  0,    0,-11, 12,
 
     0, -7,  9,    1,  0,-21,    0,  1, 21,    1,  0,-21,    0, -4, 21,
     1,  7,  0,    0, -7,-21,    1, 15,  0,    1,  0,  6,    1, -1, -6,
     0,-10, 12,
 
     0, -7,  9,    1,  0,-21,    0,  1, 21,    1,  6,-18,    0, -7, 18,
     1,  7,-21,    0,  7, 21,    1, -7,-21,    0,  7, 21,    1,  0,-21,
     0,  1, 21,    1,  0,-21,    0,-18, 21,    1,  4,  0,    0, 13,  0,
     1,  4,  0,    0,-21,-21,    1,  6,  0,    0,  8,  0,    1,  7,  0,
     0,-10, 12,
 
     0, -7,  9,    1,  0,-21,    0,  1, 21,    1, 12,-19,    0,-12, 17,
     1, 12,-19,    0,  0, 21,    1,  0,-21,    0,-16, 21,    1,  4,  0,
     0,  9,  0,    1,  6,  0,    0,-19,-21,    1,  6,  0,    0,  3, 12,
 
     0, -2,  9,    1, -3, -1,    1, -2, -2,    1, -1, -2,    1, -1, -4,
     1,  0, -3,    1,  1, -4,    1,  1, -2,    1,  2, -2,    1,  3, -1,
     1,  2,  0,    1,  3,  1,    1,  2,  2,    1,  1,  2,    1,  1,  4,
     1,  0,  3,    1, -1,  4,    1, -1,  2,    1, -2,  2,    1, -3,  1,
     1, -2,  0,    0,  0,  0,    1, -2, -1,    1, -2, -2,    1, -1, -2,
     1, -1, -4,    1,  0, -3,    1,  1, -4,    1,  1, -2,    1,  2, -2,
     1,  2, -1,    0,  2,  0,    1,  2,  1,    1,  2,  2,    1,  1,  2,
     1,  1,  4,    1,  0,  3,    1, -1,  4,    1, -1,  2,    1, -2,  2,
     1, -2,  1,    0, -2, -9,
 
     0, -7,  9,    1,  0,-21,    0,  1, 21,    1,  0,-21,    0, -4, 21,
     1, 12,  0,    1,  3, -1,    1,  1, -1,    1,  1, -2,    1,  0, -3,
     1, -1, -2,    1, -1, -1,    1, -3, -1,    1, -8,  0,    0,  8, 11,
     1,  2, -1,    1,  1, -1,    1,  1, -2,    1,  0, -3,    1, -1, -2,
     1, -1, -1,    1, -2, -1,    0,-12,-10,    1,  7,  0,    0,  1, 12,
 
     0, -2,  9,    1, -3, -1,    1, -2, -2,    1, -1, -2,    1, -1, -4,
     1,  0, -3,    1,  1, -4,    1,  1, -2,    1,  2, -2,    1,  3, -1,
     1,  2,  0,    1,  3,  1,    1,  2,  2,    1,  1,  2,    1,  1,  4,
     1,  0,  3,    1, -1,  4,    1, -1,  2,    1, -2,  2,    1, -3,  1,
     1, -2,  0,    0,  0,  0,    1, -2, -1,    1, -2, -2,    1, -1, -2,
     1, -1, -4,    1,  0, -3,    1,  1, -4,    1,  1, -2,    1,  2, -2,
     1,  2, -1,    0,  2,  0,    1,  2,  1,    1,  2,  2,    1,  1,  2,
     1,  1,  4,    1,  0,  3,    1, -1,  4,    1, -1,  2,    1, -2,  2,
     1, -2,  1,    0, -5,-19,    1,  0,  1,    1,  1,  2,    1,  2,  1,
     1,  1,  0,    1,  2, -1,    1,  1, -2,    1,  1, -7,    1,  1, -1,
     1,  2,  0,    1,  1,  2,    1,  0,  1,    0, -5,  5,    1,  1, -4,
     1,  1, -2,    1,  1, -1,    1,  1,  0,    1,  1,  1,    0, -9, 15,
 
     0, -7,  9,    1,  0,-21,    0,  1, 21,    1,  0,-21,    0, -4, 21,
     1, 12,  0,    1,  3, -1,    1,  1, -1,    1,  1, -2,    1,  0, -2,
     1, -1, -2,    1, -1, -1,    1, -3, -1,    1, -8,  0,    0,  8, 10,
     1,  2, -1,    1,  1, -1,    1,  1, -2,    1,  0, -2,    1, -1, -2,
     1, -1, -1,    1, -2, -1,    0,-12,-11,    1,  7,  0,    0,  2, 11,
     1,  2, -1,    1,  1, -1,    1,  3, -7,    1,  1, -1,    1,  1,  0,
     1,  1,  1,    0, -7,  8,    1,  1, -2,    1,  2, -7,    1,  1, -1,
     1,  2,  0,    1,  1,  2,    1,  0,  1,    0,-10,  9,
 
     0,  4,  6,    1,  1,  3,    1,  0, -6,    1, -1,  3,    1, -2,  2,
     1, -3,  1,    1, -3,  0,    1, -3, -1,    1, -2, -2,    1,  0, -2,
     1,  1, -2,    1,  1, -1,    1,  2, -1,    1,  6, -2,    1,  2, -1,
     1,  2, -2,    0,-14,  9,    1,  2, -2,    1,  2, -1,    1,  6, -2,
     1,  2, -1,    1,  1, -1,    1,  1, -2,    1,  0, -4,    1, -2, -2,
     1, -3, -1,    1, -3,  0,    1, -3,  1,    1, -2,  2,    1, -1,  3,
     1,  0, -6,    1,  1,  3,    0,  4,  9,
 
     0, -3,  9,    1,  0,-21,    0,  1, 21,    1,  0,-21,    0, -7, 21,
     1, -1, -6,    1,  0,  6,    1, 15,  0,    1,  0, -6,    1, -1,  6,
     0,-10,-21,    1,  7,  0,    0, -6, 12,
 
     0, -7,  9,    1,  0,-15,    1,  1, -3,    1,  2, -2,    1,  3, -1,
     1,  2,  0,    1,  3,  1,    1,  2,  2,    1,  1,  3,    1,  0, 15,
     0,-13,  0,    1,  0,-15,    1,  1, -3,    1,  2, -2,    1,  2, -1,
     0, -9, 21,    1,  7,  0,    0,  7,  0,    1,  6,  0,    0,-10, -9,
 
     0, -9,  9,    1,  7,-21,    0, -6, 21,    1,  6,-18,    0,  7, 18,
     1, -7,-21,    0, -9, 21,    1,  6,  0,    0,  6,  0,    1,  6,  0,
     0,-11, -9,
 
     0, -8,  9,    1,  4,-21,    0, -3, 21,    1,  3,-16,    0,  4, 16,
     1, -4,-21,    0,  4, 21,    1,  4,-21,    0, -3, 21,    1,  3,-16,
     0,  4, 16,    1, -4,-21,    0,-15, 21,    1,  7,  0,    0,  9,  0,
     1,  6,  0,    0,-11, -9,
 
     0, -9,  9,    1, 13,-21,    0,-12, 21,    1, 13,-21,    0,  0, 21,
     1,-14,-21,    0, -2, 21,    1,  6,  0,    0,  6,  0,    1,  6,  0,
     0,-18,-21,    1,  6,  0,    0,  6,  0,    1,  6,  0,    0,-11, 12,
 
     0, -9,  9,    1,  7,-11,    1,  0,-10,    0, -6, 21,    1,  7,-11,
     1,  0,-10,    0,  7, 21,    1, -7,-11,    0,-10, 11,    1,  6,  0,
     0,  7,  0,    1,  6,  0,    0,-13,-21,    1,  7,  0,    0, -5, 12,
 
     0,  4,  9,    1,-13,-21,    0, 14, 21,    1,-13,-21,    0,  0, 21,
     1, -1, -6,    1,  0,  6,    1, 14,  0,    0,-14,-21,    1, 14,  0,
     1,  0,  6,    1, -1, -6,    0, -8, 12,
 
     0, -7,  0,    1,  0, -1,    1, -1,  0,    1,  0,  1,    1,  1,  1,
     1,  2,  1,    1,  4,  0,    1,  2, -1,    1,  1, -1,    1,  1, -2,
     1,  0, -7,    1,  1, -2,    1,  1, -1,    0, -3, 12,    1,  0, -9,
     1,  1, -2,    1,  2, -1,    1,  1,  0,    0, -4, 10,    1, -1, -1,
     1, -6, -1,    1, -3, -1,    1, -1, -2,    1,  0, -2,    1,  1, -2,
     1,  3, -1,    1,  3,  0,    1,  2,  1,    1,  2,  2,    0, -7,  5,
     1, -2, -1,    1, -1, -2,    1,  0, -2,    1,  1, -2,    1,  2, -1,
     0,  1, 12,
 
     0, -7,  9,    1,  0,-21,    0,  1, 21,    1,  0,-21,    0,  0, 11,
     1,  2,  2,    1,  2,  1,    1,  2,  0,    1,  3, -1,    1,  2, -2,
     1,  1, -3,    1,  0, -2,    1, -1, -3,    1, -2, -2,    1, -3, -1,
     1, -2,  0,    1, -2,  1,    1, -2,  2,    0,  6, 11,    1,  2, -1,
     1,  2, -2,    1,  1, -3,    1,  0, -2,    1, -1, -3,    1, -2, -2,
     1, -2, -1,    0,-10, 21,    1,  4,  0,    0,  3, -9,
 
     0,  3, -1,    1, -1, -1,    1,  1, -1,    1,  1,  1,    1,  0,  1,
     1, -2,  2,    1, -2,  1,    1, -3,  0,    1, -3, -1,    1, -2, -2,
     1, -1, -3,    1,  0, -2,    1,  1, -3,    1,  2, -2,    1,  3, -1,
     1,  2,  0,    1,  3,  1,    1,  2,  2,    0, -7, 11,    1, -2, -1,
     1, -2, -2,    1, -1, -3,    1,  0, -2,    1,  1, -3,    1,  2, -2,
     1,  2, -1,    0, -2, 12,
 
     0,  3,  9,    1,  0,-21,    0,  1, 21,    1,  0,-21,    0, -1, 11,
     1, -2,  2,    1, -2,  1,    1, -2,  0,    1, -3, -1,    1, -2, -2,
     1, -1, -3,    1,  0, -2,    1,  1, -3,    1,  2, -2,    1,  3, -1,
     1,  2,  0,    1,  2,  1,    1,  2,  2,    0, -6, 11,    1, -2, -1,
     1, -2, -2,    1, -1, -3,    1,  0, -2,    1,  1, -3,    1,  2, -2,
     1,  2, -1,    0,  3, 21,    1,  4,  0,    0, -1,-21,    1,  4,  0,
     0,-10, 12,
 
     0, -8, -4,    1, 12,  0,    1,  0,  2,    1, -1,  2,    1, -1,  1,
     1, -2,  1,    1, -3,  0,    1, -3, -1,    1, -2, -2,    1, -1, -3,
     1,  0, -2,    1,  1, -3,    1,  2, -2,    1,  3, -1,    1,  2,  0,
     1,  3,  1,    1,  2,  2,    0, -1,  5,    1,  0,  3,    1, -1,  2,
     0, -5,  1,    1, -2, -1,    1, -2, -2,    1, -1, -3,    1,  0, -2,
     1,  1, -3,    1,  2, -2,    1,  2, -1,    0, -2, 12,
 
     0, -2,  8,    1, -1, -1,    1,  1, -1,    1,  1,  1,    1,  0,  1,
     1, -1,  1,    1, -2,  0,    1, -2, -1,    1, -1, -2,    1,  0,-18,
     0,  3, 21,    1, -1, -1,    1, -1, -2,    1,  0,-18,    0, -4, 14,
     1,  8,  0,    0, -8,-14,    1,  7,  0,    0, -8, 12,
 
     0, -4,  2,    1, -2, -1,    1, -1, -1,    1, -1, -2,    1,  0, -2,
     1,  1, -2,    1,  1, -1,    1,  2, -1,    1,  2,  0,    1,  2,  1,
     1,  1,  1,    1,  1,  2,    1,  0,  2,    1, -1,  2,    1, -1,  1,
     1, -2,  1,    1, -2,  0,    0, -2, -1,    1, -1, -2,    1,  0, -4,
     1,  1, -2,    0,  6,  0,    1,  1,  2,    1,  0,  4,    1, -1,  2,
     0,  1, -1,    1,  1,  1,    1,  2,  1,    1,  0, -1,    1, -2,  0,
     0, -9, -7,    1, -1, -1,    1, -1, -2,    1,  0, -1,    1,  1, -2,
     1,  3, -1,    1,  5,  0,    1,  3, -1,    1,  1, -1,    0,-13,  5,
     1,  1, -1,    1,  3, -1,    1,  5,  0,    1,  3, -1,    1,  1, -2,
     1,  0, -1,    1, -1, -2,    1, -3, -1,    1, -6,  0,    1, -3,  1,
     1, -1,  2,    1,  0,  1,    1,  1,  2,    1,  3,  1,    0,  1, 12,
 
     0, -7,  9,    1,  0,-21,    0,  1, 21,    1,  0,-21,    0,  0, 11,
     1,  2,  2,    1,  3,  1,    1,  2,  0,    1,  3, -1,    1,  1, -2,
     1,  0,-11,    0, -4, 14,    1,  2, -1,    1,  1, -2,    1,  0,-11,
     0,-14, 21,    1,  4,  0,    0, -4,-21,    1,  7,  0,    0,  4,  0,
     1,  7,  0,    0,-10, 12,
 
     0, -7,  9,    1, -1, -1,    1,  1, -1,    1,  1,  1,    1, -1,  1,
     0,  0, -7,    1,  0,-14,    0,  1, 14,    1,  0,-14,    0, -4, 14,
     1,  4,  0,    0, -4,-14,    1,  7,  0,    0,-10, 12,
 
     0, -6,  9,    1, -1, -1,    1,  1, -1,    1,  1,  1,    1, -1,  1,
     0,  1, -7,    1,  0,-18,    1, -1, -2,    1, -2, -1,    1, -2,  0,
     1, -1,  1,    1,  0,  1,    1,  1,  1,    1,  1, -1,    1, -1, -1,
     0,  4, 20,    1,  0,-18,    1, -1, -2,    1, -1, -1,    0, -1, 21,
     1,  4,  0,    0, -8, -2,
 
     0, -7,  9,    1,  0,-21,    0,  1, 21,    1,  0,-21,    0, 10, 14,
     1,-10,-10,    0,  5,  4,    1,  6, -8,    0, -7,  8,    1,  6, -8,
     0,-14, 21,    1,  4,  0,    0,  7, -7,    1,  6,  0,    0,-17,-14,
     1,  7,  0,    0,  4,  0,    1,  6,  0,    0,-10, 12,
 
     0, -7,  9,    1,  0,-21,    0,  1, 21,    1,  0,-21,    0, -4, 21,
     1,  4,  0,    0, -4,-21,    1,  7,  0,    0,-10, 12,
 
     0, -7,  2,    1,  0,-14,    0,  1, 14,    1,  0,-14,    0,  0, 11,
     1,  2,  2,    1,  3,  1,    1,  2,  0,    1,  3, -1,    1,  1, -2,
     1,  0,-11,    0, -4, 14,    1,  2, -1,    1,  1, -2,    1,  0,-11,
     0,  1, 11,    1,  2,  2,    1,  3,  1,    1,  2,  0,    1,  3, -1,
     1,  1, -2,    1,  0,-11,    0, -4, 14,    1,  2, -1,    1,  1, -2,
     1,  0,-11,    0,-25, 14,    1,  4,  0,    0, -4,-14,    1,  7,  0,
     0,  4,  0,    1,  7,  0,    0,  4,  0,    1,  7,  0,    0,-10, 12,
 
     0, -7,  2,    1,  0,-14,    0,  1, 14,    1,  0,-14,    0,  0, 11,
     1,  2,  2,    1,  3,  1,    1,  2,  0,    1,  3, -1,    1,  1, -2,
     1,  0,-11,    0, -4, 14,    1,  2, -1,    1,  1, -2,    1,  0,-11,
     0,-14, 14,    1,  4,  0,    0, -4,-14,    1,  7,  0,    0,  4,  0,
     1,  7,  0,    0,-10, 12,
 
     0, -3,  2,    1, -3, -1,    1, -2, -2,    1, -1, -3,    1,  0, -2,
     1,  1, -3,    1,  2, -2,    1,  3, -1,    1,  2,  0,    1,  3,  1,
     1,  2,  2,    1,  1,  3,    1,  0,  2,    1, -1,  3,    1, -2,  2,
     1, -3,  1,    1, -2,  0,    0,  0,  0,    1, -2, -1,    1, -2, -2,
     1, -1, -3,    1,  0, -2,    1,  1, -3,    1,  2, -2,    1,  2, -1,
     0,  2,  0,    1,  2,  1,    1,  2,  2,    1,  1,  3,    1,  0,  2,
     1, -1,  3,    1, -2,  2,    1, -2,  1,    0, -3, -2,
 
     0, -7,  2,    1,  0,-21,    0,  1, 21,    1,  0,-21,    0,  0, 18,
     1,  2,  2,    1,  2,  1,    1,  2,  0,    1,  3, -1,    1,  2, -2,
     1,  1, -3,    1,  0, -2,    1, -1, -3,    1, -2, -2,    1, -3, -1,
     1, -2,  0,    1, -2,  1,    1, -2,  2,    0,  6, 11,    1,  2, -1,
     1,  2, -2,    1,  1, -3,    1,  0, -2,    1, -1, -3,    1, -2, -2,
     1, -2, -1,    0,-10, 14,    1,  4,  0,    0, -4,-21,    1,  7,  0,
     0,  0, 19,
 
     0,  3,  2,    1,  0,-21,    0,  1, 21,    1,  0,-21,    0, -1, 18,
     1, -2,  2,    1, -2,  1,    1, -2,  0,    1, -3, -1,    1, -2, -2,
     1, -1, -3,    1,  0, -2,    1,  1, -3,    1,  2, -2,    1,  3, -1,
     1,  2,  0,    1,  2,  1,    1,  2,  2,    0, -6, 11,    1, -2, -1,
     1, -2, -2,    1, -1, -3,    1,  0, -2,    1,  1, -3,    1,  2, -2,
     1,  2, -1,    0,  3, -7,    1,  7,  0,    0,-11, 19,
 
     0, -7,  2,    1,  0,-14,    0,  1, 14,    1,  0,-14,    0,  0,  8,
     1,  1,  3,    1,  2,  2,    1,  2,  1,    1,  3,  0,    1,  1, -1,
     1,  0, -1,    1, -1, -1,    1, -1,  1,    1,  1,  1,    0,-12,  1,
     1,  4,  0,    0, -4,-14,    1,  7,  0,    0, -4, 12,
 
     0,  1,  0,    1,  1,  2,    1,  0, -4,    1, -1,  2,    1, -1,  1,
     1, -2,  1,    1, -4,  0,    1, -2, -1,    1, -1, -1,    1,  0, -2,
     1,  1, -1,    1,  2, -1,    1,  5, -2,    1,  2, -1,    1,  1, -1,
     0,-11,  7,    1,  1, -1,    1,  2, -1,    1,  5, -2,    1,  2, -1,
     1,  1, -1,    1,  0, -3,    1, -1, -1,    1, -2, -1,    1, -4,  0,
     1, -2,  1,    1, -1,  1,    1, -1,  2,    1,  0, -4,    1,  1,  2,
     0,  1, 10,
 
     0, -7,  9,    1,  0,-17,    1,  1, -3,    1,  2, -1,    1,  2,  0,
     1,  2,  1,    1,  1,  2,    0, -7, 18,    1,  0,-17,    1,  1, -3,
     1,  1, -1,    0, -6, 14,    1,  8,  0,    0, -7, -2,
 
     0, -7,  2,    1,  0,-11,    1,  1, -2,    1,  3, -1,    1,  2,  0,
     1,  3,  1,    1,  2,  2,    0,-10, 11,    1,  0,-11,    1,  1, -2,
     1,  2, -1,    0,  7, 14,    1,  0,-14,    0,  1, 14,    1,  0,-14,
     0,-15, 14,    1,  4,  0,    0,  7,  0,    1,  4,  0,    0, -1,-14,
     1,  4,  0,    0,-10, 12,
 
     0, -9,  2,    1,  6,-14,    0, -5, 14,    1,  5,-12,    0,  6, 12,
     1, -6,-14,    0, -8, 14,    1,  6,  0,    0,  4,  0,    1,  6,  0,
     0,-11, -2,
 
     0, -8,  2,    1,  4,-14,    0, -3, 14,    1,  3,-11,    0,  4, 11,
     1, -4,-14,    0,  4, 14,    1,  4,-14,    0, -3, 14,    1,  3,-11,
     0,  4, 11,    1, -4,-14,    0,-15, 14,    1,  7,  0,    0,  9,  0,
     1,  6,  0,    0,-11, -2,
 
     0, -8,  2,    1, 11,-14,    0,-10, 14,    1, 11,-14,    0,  0, 14,
     1,-12,-14,    0, -2, 14,    1,  6,  0,    0,  4,  0,    1,  6,  0,
     0,-16,-14,    1,  6,  0,    0,  4,  0,    1,  6,  0,    0,-10, 12,
 
     0, -8,  2,    1,  6,-14,    0, -5, 14,    1,  5,-12,    0,  6, 12,
     1, -6,-14,    1, -2, -4,    1, -2, -2,    1, -2, -1,    1, -1,  0,
     1, -1,  1,    1,  1,  1,    1,  1, -1,    0, -2, 20,    1,  6,  0,
     0,  4,  0,    1,  6,  0,    0,-11, -2,
 
     0,  2,  2,    1,-11,-14,    0, 12, 14,    1,-11,-14,    0,  0, 14,
     1, -1, -4,    1,  0,  4,    1, 12,  0,    0,-12,-14,    1, 12,  0,
     1,  0,  4,    1, -1, -4,    0, -8, 12,
 
     0, -3,  9,    1, -3, -1,    1, -2, -3,    1, -1, -5,    1,  0, -3,
     1,  1, -5,    1,  2, -3,    1,  3, -1,    1,  2,  0,    1,  3,  1,
     1,  2,  3,    1,  1,  5,    1,  0,  3,    1, -1,  5,    1, -2,  3,
     1, -3,  1,    1, -2,  0,    0,  0,  0,    1, -2, -1,    1, -1, -1,
     1, -1, -2,    1, -1, -5,    1,  0, -3,    1,  1, -5,    1,  1, -2,
     1,  1, -1,    1,  2, -1,    0,  2,  0,    1,  2,  1,    1,  1,  1,
     1,  1,  2,    1,  1,  5,    1,  0,  3,    1, -1,  5,    1, -1,  2,
     1, -1,  1,    1, -2,  1,    0, -3, -9,
 
     0, -6,  5,    1,  2,  1,    1,  3,  3,    1,  0,-21,    0, -1, 20,
     1,  0,-20,    0, -4,  0,    1,  9,  0,    0, -7, 12,
 
     0, -8,  5,    1,  1, -1,    1, -1, -1,    1, -1,  1,    1,  0,  1,
     1,  1,  2,    1,  1,  1,    1,  3,  1,    1,  4,  0,    1,  3, -1,
     1,  1, -1,    1,  1, -2,    1,  0, -2,    1, -1, -2,    1, -3, -2,
     1, -5, -2,    1, -2, -1,    1, -2, -2,    1, -1, -3,    1,  0, -3,
     0,  9, 21,    1,  2, -1,    1,  1, -1,    1,  1, -2,    1,  0, -2,
     1, -1, -2,    1, -3, -2,    1, -4, -2,    0, -5, -7,    1,  1,  1,
     1,  2,  0,    1,  5, -2,    1,  3,  0,    1,  2,  1,    1,  1,  1,
     0,-11,  0,    1,  5, -3,    1,  4,  0,    1,  1,  1,    1,  1,  2,
     1,  0,  2,    0, -9,  7,
 
     0, -8,  5,    1,  1, -1,    1, -1, -1,    1, -1,  1,    1,  0,  1,
     1,  1,  2,    1,  1,  1,    1,  3,  1,    1,  4,  0,    1,  3, -1,
     1,  1, -2,    1,  0, -3,    1, -1, -2,    1, -3, -1,    1, -3,  0,
     0,  3,  9,    1,  2, -1,    1,  1, -2,    1,  0, -3,    1, -1, -2,
     1, -2, -1,    0,  0,  0,    1,  2, -1,    1,  2, -2,    1,  1, -2,
     1,  0, -3,    1, -1, -2,    1, -1, -1,    1, -3, -1,    1, -4,  0,
     1, -3,  1,    1, -1,  1,    1, -1,  2,    1,  0,  1,    1,  1,  1,
     1,  1, -1,    1, -1, -1,    0, 11,  6,    1,  1, -3,    1,  0, -3,
     1, -1, -2,    1, -1, -1,    1, -2, -1,    0, -4, 12,
 
     0,  0,  7,    1,  0,-19,    0,  1, 21,    1,  0,-21,    0,  0, 21,
     1,-11,-15,    1, 16,  0,    0, -9, -6,    1,  7,  0,    0, -8, 12,
 
     0, -7,  9,    1, -2,-10,    0,  0,  0,    1,  2,  2,    1,  3,  1,
     1,  3,  0,    1,  3, -1,    1,  2, -2,    1,  1, -3,    1,  0, -2,
     1, -1, -3,    1, -2, -2,    1, -3, -1,    1, -3,  0,    1, -3,  1,
     1, -1,  1,    1, -1,  2,    1,  0,  1,    1,  1,  1,    1,  1, -1,
     1, -1, -1,    0,  7, 10,    1,  2, -1,    1,  2, -2,    1,  1, -3,
     1,  0, -2,    1, -1, -3,    1, -2, -2,    1, -2, -1,    0, -6, 21,
     1, 10,  0,    0,-10, -1,    1,  5,  0,    1,  5,  1,    0, -7, -9,
 
     0,  3,  6,    1, -1, -1,    1,  1, -1,    1,  1,  1,    1,  0,  1,
     1, -1,  2,    1, -2,  1,    1, -3,  0,    1, -3, -1,    1, -2, -2,
     1, -1, -2,    1, -1, -4,    1,  0, -6,    1,  1, -3,    1,  2, -2,
     1,  3, -1,    1,  2,  0,    1,  3,  1,    1,  2,  2,    1,  1,  3,
     1,  0,  1,    1, -1,  3,    1, -2,  2,    1, -3,  1,    1, -1,  0,
     1, -3, -1,    1, -2, -2,    1, -1, -3,    0,  6, 14,    1, -2, -1,
     1, -2, -2,    1, -1, -2,    1, -1, -4,    1,  0, -6,    1,  1, -3,
     1,  2, -2,    1,  2, -1,    0,  2,  0,    1,  2,  1,    1,  2,  2,
     1,  1,  3,    1,  0,  1,    1, -1,  3,    1, -2,  2,    1, -2,  1,
     0, -3, -1,
 
     0, -9,  9,    1,  0, -6,    0,  0,  2,    1,  1,  2,    1,  2,  2,
     1,  2,  0,    1,  5, -3,    1,  2,  0,    1,  1,  1,    1,  1,  2,
     0,-13, -2,    1,  2,  1,    1,  2,  0,    1,  5, -2,    0,  4,  3,
     1,  0, -3,    1, -1, -3,    1, -4, -5,    1, -1, -2,    1, -1, -3,
     1,  0, -5,    0,  6, 15,    1, -5, -5,    1, -1, -2,    1, -1, -3,
     1,  0, -5,    0, -1, 12,
 
     0, -4,  9,    1, -3, -1,    1, -1, -2,    1,  0, -3,    1,  1, -2,
     1,  3, -1,    1,  4,  0,    1,  3,  1,    1,  1,  2,    1,  0,  3,
     1, -1,  2,    1, -3,  1,    1, -4,  0,    0,  0,  0,    1, -2, -1,
     1, -1, -2,    1,  0, -3,    1,  1, -2,    1,  2, -1,    0,  4,  0,
     1,  2,  1,    1,  1,  2,    1,  0,  3,    1, -1,  2,    1, -2,  1,
     0, -4, -9,    1, -3, -1,    1, -1, -1,    1, -1, -2,    1,  0, -4,
     1,  1, -2,    1,  1, -1,    1,  3, -1,    1,  4,  0,    1,  3,  1,
     1,  1,  1,    1,  1,  2,    1,  0,  4,    1, -1,  2,    1, -1,  1,
     1, -3,  1,    0, -4,  0,    1, -2, -1,    1, -1, -1,    1, -1, -2,
     1,  0, -4,    1,  1, -2,    1,  1, -1,    1,  2, -1,    0,  4,  0,
     1,  2,  1,    1,  1,  1,    1,  1,  2,    1,  0,  4,    1, -1,  2,
     1, -1,  1,    1, -2,  1,    0, -4,  0,
 
     0,  4,  2,    1, -1, -3,    1, -2, -2,    1, -3, -1,    1, -1,  0,
     1, -3,  1,    1, -2,  2,    1, -1,  3,    1,  0,  1,    1,  1,  3,
     1,  2,  2,    1,  3,  1,    1,  2,  0,    1,  3, -1,    1,  2, -2,
     1,  1, -3,    1,  0, -6,    1, -1, -4,    1, -1, -2,    1, -2, -2,
     1, -3, -1,    1, -3,  0,    1, -2,  1,    1, -1,  2,    1,  0,  1,
     1,  1,  1,    1,  1, -1,    1, -1, -1,    0,  4,  5,    1, -2,  1,
     1, -2,  2,    1, -1,  3,    1,  0,  1,    1,  1,  3,    1,  2,  2,
     1,  2,  1,    0,  2,  0,    1,  2, -1,    1,  2, -2,    1,  1, -3,
     1,  0, -6,    1, -1, -4,    1, -1, -2,    1, -2, -2,    1, -2, -1,
     0, -2, 12,
 
     0, -8,  0,
 
     0,  1,  6,    1,  0,-18,    0, -9,  9,    1, 18,  0,    0, -8,  3,
 
     0, -8, -3,    1, 18,  0,    0, -8,  3,
 
     0, -5,  4,    1,  6,-14,    0,  0, 14,    1, -6,-14,    0, -4, 10,
     1, 14, -6,    0,  0,  6,    1,-14, -6,    0,  5,  6,
 
     0,  8, 13,    1,-18,-32,    0,  8, 19,
 
     0, -8,  0,    1, 18,  0,    0,-18, -6,    1, 18,  0,    0, -8,  6,
 
     0, -7,-10,    1, -1, -1,    1,  1, -1,    1,  1,  1,    1, -1,  1,
     0, -7, 10,
 
     0, -7,-12,    1, -1,  1,    1,  1,  1,    1,  1, -1,    1,  0, -2,
     1, -1, -2,    1, -1, -1,    0, -6, 16,
 
     0, -1, 13,    1, -2, -2,    1, -2, -3,    1, -2, -4,    1, -1, -5,
     1,  0, -4,    1,  1, -5,    1,  2, -4,    1,  2, -3,    1,  2, -2,
     0, -2, 30,    1, -2, -4,    1, -1, -3,    1, -1, -5,    1,  0, -4,
     1,  1, -5,    1,  1, -3,    1,  2, -4,    0, -7, 17,
 
     0, -9, 13,    1,  2, -2,    1,  2, -3,    1,  2, -4,    1,  1, -5,
     1,  0, -4,    1, -1, -5,    1, -2, -4,    1, -2, -3,    1, -2, -2,
     0,  2, 30,    1,  2, -4,    1,  1, -3,    1,  1, -5,    1,  0, -4,
     1, -1, -5,    1, -1, -3,    1, -2, -4,    0, -3, 17,
 
     0, -7,  2,    1, -1, -1,    1,  1, -1,    1,  1,  1,    1, -1,  1,
     0,  0,-12,    1, -1, -1,    1,  1, -1,    1,  1,  1,    1, -1,  1,
     0, -7, 10,
 
     0, -7,  2,    1, -1, -1,    1,  1, -1,    1,  1,  1,    1, -1,  1,
     0,  0,-14,    1, -1,  1,    1,  1,  1,    1,  1, -1,    1,  0, -2,
     1, -1, -2,    1, -1, -1,    0, -6, 16,
 
     0, -7,  9,    1, -1, -2,    1,  1,-12,    1,  1, 12,    1, -1,  2,
     0,  0, -2,    1,  0, -6,    0,  0,-11,    1, -1, -1,    1,  1, -1,
     1,  1,  1,    1, -1,  1,    0, -7, 10,
 
     0, -8,  5,    1,  1, -1,    1, -1, -1,    1, -1,  1,    1,  0,  1,
     1,  1,  2,    1,  1,  1,    1,  2,  1,    1,  3,  0,    1,  3, -1,
     1,  1, -1,    1,  1, -2,    1,  0, -2,    1, -1, -2,    1, -1, -1,
     1, -4, -2,    1,  0, -3,    0,  1, 14,    1,  2, -1,    1,  1, -1,
     1,  1, -2,    1,  0, -2,    1, -1, -2,    1, -2, -2,    0, -2, -9,
     1, -1, -1,    1,  1, -1,    1,  1,  1,    1, -1,  1,    0, -3, 10,
 
     0, -8,  9,    1, -1, -7,    0,  2,  7,    1, -2, -7,    0, -7, -2,
 
     0, -8,  9,    1, -1, -7,    0,  2,  7,    1, -2, -7,    0,  9,  7,
     1, -1, -7,    0,  2,  7,    1, -2, -7,    0, -7, -2,
 
     0, -4, 13,    1,  0,-29,    0,  4, 29,    1,  0,-29,    0,  4, 22,
     1, -1, -1,    1,  1, -1,    1,  1,  1,    1,  0,  1,    1, -2,  2,
     1, -3,  1,    1, -4,  0,    1, -3, -1,    1, -2, -2,    1,  0, -2,
     1,  1, -2,    1,  1, -1,    1,  2, -1,    1,  6, -2,    1,  2, -1,
     1,  2, -2,    0,-14,  9,    1,  2, -2,    1,  2, -1,    1,  6, -2,
     1,  2, -1,    1,  1, -1,    1,  1, -2,    1,  0, -4,    1, -2, -2,
     1, -3, -1,    1, -4,  0,    1, -3,  1,    1, -2,  2,    1,  0,  1,
     1,  1,  1,    1,  1, -1,    1, -1, -1,    0,  4,  9,
 
     0,  9,  1,    1, -1, -1,    1,  1, -1,    1,  1,  1,    1,  0,  1,
     1, -1,  1,    1, -1,  0,    1, -1, -1,    1, -1, -2,    1, -2, -5,
     1, -2, -3,    1, -2, -2,    1, -2, -1,    1, -3,  0,    1, -3,  1,
     1, -1,  2,    1,  0,  3,    1,  1,  2,    1,  6,  4,    1,  2,  2,
     1,  1,  2,    1,  0,  2,    1, -1,  2,    1, -2,  1,    1, -2, -1,
     1, -1, -2,    1,  0, -2,    1,  1, -3,    1,  2, -3,    1,  5, -7,
     1,  2, -2,    1,  3, -1,    1,  1,  0,    1,  1,  1,    1,  0,  1,
     0,-15, -2,    1, -2,  1,    1, -1,  2,    1,  0,  3,    1,  1,  2,
     1,  2,  2,    0,  0,  6,    1,  1, -2,    1,  8,-11,    1,  2, -2,
     1,  2, -1,    0, -7, 12,
 
     0,  6,  1,    1, -1,  2,    1, -2,  1,    1, -3,  0,    1, -2, -1,
     1, -1, -1,    1, -1, -3,    1,  0, -3,    1,  1, -2,    1,  2, -1,
     1,  3,  0,    1,  2,  1,    1,  1,  2,    0, -5,  8,    1, -2, -2,
     1, -1, -3,    1,  0, -3,    1,  1, -2,    1,  1, -1,    0,  7, 11,
     1, -1, -8,    1,  0, -2,    1,  2, -1,    1,  2,  0,    1,  2,  2,
     1,  1,  3,    1,  0,  2,    1, -1,  3,    1, -1,  2,    1, -2,  2,
     1, -2,  1,    1, -3,  1,    1, -3,  0,    1, -3, -1,    1, -2, -1,
     1, -2, -2,    1, -1, -2,    1, -1, -3,    1,  0, -3,    1,  1, -3,
     1,  1, -2,    1,  2, -2,    1,  2, -1,    1,  3, -1,    1,  3,  0,
     1,  3,  1,    1,  2,  1,    1,  1,  1,    0, -2, 13,    1, -1, -8,
     1,  0, -2,    1,  1, -1,    0, -4,  7,
 
     0,  9,  9,    1,-18,-21,    0,  5, 21,    1,  2, -2,    1,  0, -2,
     1, -1, -2,    1, -2, -1,    1, -2,  0,    1, -2,  2,    1,  0,  2,
     1,  1,  2,    1,  2,  1,    1,  2,  0,    1,  2, -1,    1,  3, -1,
     1,  3,  0,    1,  3,  1,    1,  2,  1,    0, -4,-14,    1, -2, -1,
     1, -1, -2,    1,  0, -2,    1,  2, -2,    1,  2,  0,    1,  2,  1,
     1,  1,  2,    1,  0,  2,    1, -2,  2,    1, -2,  0,    0, -5,  5,
 
     0, -8, 13,    1,  0,-32,    0, -8, 19,
 
     0,-10,-14,    1, 18,  0,    0,-10, 14,
 
     0,-10, 13,    1, 18,-32,    0,-10, 19,
 
     0, -8, 13,    1,  0,-32,    0,  1, 32,    1,  0,-32,    0, -1, 32,
     1,  7,  0,    0, -7,-32,    1,  7,  0,    0, -9, 19,
 
     0, -3, 13,    1,  0,-32,    0,  1, 32,    1,  0,-32,    0, -7, 32,
     1,  7,  0,    0, -7,-32,    1,  7,  0,    0, -8, 19,
 
     0, -3, 13,    1, -3, -3,    1, -1, -3,    1,  0, -2,    1,  1, -3,
     1,  3, -3,    0, -2, 12,    1, -1, -3,    1,  0, -4,    1,  1, -3,
     0,  2, -2,    1, -3, -2,    1,  3, -2,    0,  0,  0,    1, -3, -3,
     1, -1, -3,    1,  0, -2,    1,  1, -3,    1,  3, -3,    0, -2, 12,
     1, -1, -3,    1,  0, -4,    1,  1, -3,    0, -5, 17,
 
     0, -7, 13,    1,  3, -3,    1,  1, -3,    1,  0, -2,    1, -1, -3,
     1, -3, -3,    0,  2, 12,    1,  1, -3,    1,  0, -4,    1, -1, -3,
     0, -2, -2,    1,  3, -2,    1, -3, -2,    0,  0,  0,    1,  3, -3,
     1,  1, -3,    1,  0, -2,    1, -1, -3,    1, -3, -3,    0,  2, 12,
     1,  1, -3,    1,  0, -4,    1, -1, -3,    0, -5, 17,
 
     0, -8,  9,    1,  1, -7,    0, -2,  7,    1,  2, -7,    0, -9, -2,
 
     0, -9, -5,    1,  8,  5,    1,  8, -5,    0,-16,  0,    1,  8,  4,
     1,  8, -4,    0, -9,  5,
 
     0,  8,  6,    1,-16, -9,    1, 16, -9,    0, -8, 12,
 
     0, -8,  6,    1, 16, -9,    1,-16, -9,    0,  8, 12};
 
 static short dstart[128]={
  1572, 1572, 1572, 1572, 1572, 1572, 1572, 1572,
  1572, 1572, 1572, 1572, 1572, 1572, 1572, 1572,
  1572, 1572, 1572, 1572, 1572, 1572, 1572, 1572,
  1572, 1572, 1572, 1572, 1572, 1572, 1572, 1572,
  1572, 1674, 1722, 1572, 1731, 1870, 1770, 1717,
  1612, 1631, 1581, 1573, 1604, 1578, 1598, 1590,
  1217, 1255, 1264, 1306, 1350, 1360, 1395, 1441,
  1468, 1526, 1650, 1661, 1987, 1593, 1991, 1687,
  1817,    0,   13,   53,   84,  111,  128,  143,
   179,  198,  207,  225,  244,  255,  276,  291,
   333,  358,  418,  457,  490,  503,  523,  534,
   551,  566,  581, 1909, 1906, 1918, 1980, 1903,
  1975,  594,  630,  659,  686,  717,  746,  765,
   820,  842,  856,  878,  897,  906,  941,  963,
   997, 1028, 1057, 1076, 1107, 1121, 1143, 1154,
  1171, 1186, 1204, 1927, 1900, 1951, 1572, 1572};

 static short dlength[128]={
     1,    1,    1,    1,    1,    1,    1,    1,
     1,    1,    1,    1,    1,    1,    1,    1,
     1,    1,    1,    1,    1,    1,    1,    1,
     1,    1,    1,    1,    1,    1,    1,    1,
     1,   13,    9,    1,   39,   30,   47,    5,
    19,   19,    9,    5,    8,    3,    6,    3,
    38,    9,   42,   44,   10,   35,   46,   27,
    58,   46,   11,   13,    4,    5,    4,   30,
    53,   13,   40,   31,   27,   17,   15,   36,
    19,    9,   18,   19,   11,   21,   15,   42,
    25,   60,   39,   33,   13,   20,   11,   17,
    15,   15,   13,    9,    3,    9,    7,    3,
     5,   36,   29,   27,   31,   29,   19,   55,
    22,   14,   22,   19,    9,   35,   22,   34,
    31,   29,   19,   31,   14,   22,   11,   17,
    15,   18,   13,   24,    3,   24,    1,    1};

