#include <array>
#include <cmath>
#include <queue>
#include <sstream>
#include <stack>
#include <thread>
#include <utility>
#include <vector>
#include "AI.h"
#include "constants.h"
#define PI 3.14159265358979323846
short map[2][48][48][48][48] = {
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,
1,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,-1,24,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,-1,44,44,45,46,47,
2,2,2,3,-1,6,-1,8,8,9,10,11,12,13,14,-1,-1,18,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,-1,-1,-1,-1,-1,46,46,47,
3,3,3,3,-1,-1,-1,-1,9,9,10,11,12,13,-1,-1,-1,19,19,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,-1,-1,46,46,47,
-1,4,4,4,5,-1,-1,-1,10,10,10,-1,-1,-1,-1,-1,-1,-1,-1,20,20,-1,-1,24,24,-1,-1,-1,-1,-1,-1,32,-1,34,34,35,36,37,38,39,40,41,42,43,44,45,46,47,
-1,5,5,5,5,6,7,8,9,10,11,12,13,14,-1,-1,-1,-1,-1,21,21,-1,-1,25,25,-1,38,37,36,35,34,33,-1,-1,-1,-1,37,-1,-1,-1,-1,-1,-1,44,44,45,46,47,
-1,6,6,6,6,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,-1,38,37,36,35,34,34,35,36,37,38,38,39,40,41,42,43,-1,45,45,45,46,47,
8,7,7,7,7,7,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,-1,38,37,36,36,-1,35,35,36,37,38,39,39,40,41,42,43,-1,46,46,46,46,47,
8,8,8,8,8,8,8,8,9,10,11,12,13,14,15,-1,-1,19,19,20,21,22,23,24,25,-1,38,37,37,37,37,36,36,36,37,38,39,40,40,41,42,43,-1,-1,-1,-1,-1,48,
9,9,9,-1,-1,-1,-1,-1,-1,-1,-1,13,13,14,15,16,17,18,19,20,21,22,23,24,25,-1,-1,-1,-1,-1,-1,-1,-1,-1,38,38,39,-1,41,41,42,43,44,44,45,46,-1,49,
10,10,10,-1,18,18,18,18,19,20,-1,14,14,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,-1,39,39,39,-1,-1,-1,-1,43,43,44,45,46,-1,50,
11,11,11,-1,17,17,17,18,19,20,-1,-1,15,-1,-1,-1,-1,-1,-1,21,-1,-1,24,24,25,-1,28,28,29,30,31,32,33,-1,38,38,38,38,39,40,41,42,43,44,45,46,-1,50,
12,12,12,-1,16,16,17,18,19,19,18,17,16,17,18,19,20,21,22,22,23,-1,25,25,25,26,27,28,29,30,-1,33,33,-1,37,37,37,38,39,40,41,42,-1,-1,-1,-1,-1,49,
13,13,13,14,15,16,17,18,19,19,18,17,17,17,18,19,20,21,22,23,23,-1,-1,26,26,26,27,28,29,-1,-1,-1,-1,-1,36,36,37,38,39,40,41,42,-1,45,45,46,47,48,
14,14,14,-1,16,16,17,18,19,19,18,18,18,18,18,19,20,21,22,23,24,25,-1,27,27,27,27,28,29,-1,33,33,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,
-1,-1,-1,-1,17,17,17,18,19,20,-1,19,19,19,19,19,20,21,22,23,24,25,-1,28,28,28,28,28,29,-1,32,32,33,34,35,36,37,38,39,40,41,42,-1,-1,46,46,47,48,
22,21,20,19,18,18,18,18,19,20,-1,20,20,20,20,20,20,21,22,23,24,25,-1,29,29,29,29,29,29,30,31,32,33,34,-1,-1,-1,-1,40,40,41,42,43,-1,-1,47,47,48,
22,21,20,20,-1,19,19,19,19,20,-1,21,21,21,21,21,21,21,22,-1,-1,26,-1,30,30,30,-1,-1,-1,-1,32,32,33,34,35,36,37,38,39,40,41,42,43,44,-1,48,48,48,
22,21,21,21,21,20,20,20,20,20,-1,22,22,22,22,22,22,22,22,-1,28,27,28,29,30,31,32,33,34,34,33,33,33,34,35,36,37,38,39,40,-1,43,43,44,-1,49,49,49,
22,22,22,22,21,21,21,-1,-1,-1,-1,-1,-1,-1,23,23,23,23,23,-1,28,28,28,29,30,31,-1,-1,-1,34,34,34,34,34,35,36,37,38,39,-1,-1,-1,-1,-1,-1,50,50,50,
-1,-1,-1,22,22,22,22,23,24,25,26,27,26,25,24,24,24,24,24,-1,-1,29,29,29,-1,32,33,34,-1,35,35,35,35,35,35,36,-1,-1,-1,-1,-1,49,49,50,51,51,51,51,
37,37,-1,23,23,23,23,23,24,25,26,27,26,25,25,25,25,-1,25,26,-1,30,30,30,31,32,33,34,-1,-1,-1,-1,-1,-1,-1,-1,-1,45,45,46,47,48,49,50,-1,52,52,52,
36,36,-1,24,24,24,24,24,24,25,-1,27,26,26,26,26,26,27,26,26,-1,31,31,31,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,-1,-1,53,-1,53,
35,36,-1,25,25,25,25,25,25,25,26,27,27,27,27,27,27,27,27,-1,-1,32,32,32,32,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,-1,-1,-1,-1,52,53,54,54,
34,-1,-1,26,26,26,26,26,26,26,26,27,28,28,28,28,28,28,28,-1,34,33,33,33,33,33,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,-1,51,51,-1,54,54,
33,-1,28,27,27,27,27,27,-1,27,-1,-1,-1,29,29,29,-1,-1,-1,-1,34,34,34,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,41,-1,-1,44,44,45,46,47,48,49,50,51,52,53,54,
32,-1,28,28,28,28,28,28,-1,28,29,30,-1,30,30,30,-1,38,37,36,35,35,35,-1,48,49,49,48,47,46,45,44,43,42,43,-1,-1,-1,-1,47,47,48,49,50,51,52,53,54,
31,30,29,29,29,29,29,29,-1,29,29,30,-1,31,-1,-1,-1,37,37,36,36,-1,-1,-1,47,-1,48,48,47,46,45,44,43,43,43,44,45,46,47,48,48,48,49,50,51,52,53,54,
32,-1,30,30,30,30,30,30,-1,-1,30,30,31,32,33,34,35,36,37,37,-1,-1,47,46,46,46,47,48,47,46,45,44,44,44,44,44,45,46,-1,-1,-1,-1,50,50,51,52,53,54,
33,-1,31,31,31,31,-1,31,32,-1,31,31,31,32,33,34,35,36,37,38,-1,-1,47,46,45,46,47,48,47,46,45,45,45,45,45,45,45,46,47,48,49,-1,-1,51,51,52,53,54,
34,-1,-1,-1,-1,32,33,32,32,-1,32,32,32,32,33,34,-1,-1,-1,-1,-1,-1,-1,-1,44,-1,-1,-1,-1,-1,-1,-1,-1,46,46,46,46,46,47,48,49,50,-1,-1,52,52,53,54,
35,36,37,38,-1,-1,-1,-1,-1,-1,33,33,33,33,33,34,35,36,37,38,39,40,41,42,43,44,-1,53,52,51,50,49,48,47,47,47,47,47,47,48,49,50,51,-1,53,53,53,54,
36,36,37,38,39,39,38,37,36,35,34,34,34,34,34,34,-1,37,37,38,39,40,41,42,43,44,-1,52,52,51,50,49,48,48,48,48,48,48,48,-1,50,50,51,-1,54,54,54,54,
37,37,37,38,-1,39,38,37,36,35,35,35,35,35,35,-1,-1,38,38,38,39,40,41,42,43,44,-1,52,51,51,50,49,49,49,49,49,49,49,49,50,51,51,51,-1,55,55,55,55,
38,38,38,-1,-1,-1,-1,-1,36,36,36,36,36,36,36,-1,40,39,39,39,39,40,41,42,43,44,-1,52,51,50,50,50,50,50,50,50,50,50,50,50,51,52,52,-1,56,56,56,56,
-1,39,39,40,41,-1,39,38,37,37,37,37,37,37,37,38,39,40,40,40,40,40,41,-1,44,44,-1,-1,-1,49,49,50,51,51,51,51,51,51,51,51,51,52,-1,-1,57,57,57,57,
-1,-1,40,40,41,40,39,38,38,38,-1,-1,-1,-1,-1,-1,40,40,41,41,41,41,41,42,43,44,45,46,47,48,49,50,51,52,52,52,52,-1,-1,-1,-1,53,-1,57,57,58,58,58,
-1,-1,41,41,41,40,39,39,39,39,-1,46,45,44,43,42,41,41,41,42,42,42,42,42,43,44,45,46,47,48,49,-1,-1,-1,-1,-1,-1,-1,57,56,55,54,55,56,57,58,59,59,
44,43,42,42,41,40,40,-1,-1,-1,-1,46,45,44,43,42,42,42,42,42,43,43,43,43,43,44,45,46,47,48,49,-1,-1,57,57,57,57,58,57,56,55,55,55,56,57,58,59,60,
44,43,43,42,41,41,41,-1,50,49,49,-1,45,44,43,43,43,43,43,43,43,44,44,44,44,44,45,46,47,48,49,-1,57,56,56,56,57,58,57,56,56,56,56,56,57,58,-1,61,
44,44,43,42,42,42,42,-1,50,49,48,47,46,-1,-1,-1,44,-1,44,44,-1,-1,-1,45,45,45,45,46,47,48,49,-1,57,56,55,56,57,58,57,57,57,57,57,57,57,58,-1,62,
45,44,43,43,43,43,43,-1,-1,-1,-1,-1,-1,-1,47,46,45,-1,45,-1,53,53,-1,46,46,46,46,46,47,48,49,-1,-1,-1,54,-1,-1,-1,58,58,58,58,58,58,58,58,-1,63,
45,44,44,44,44,44,44,45,46,47,48,49,49,48,47,46,46,-1,-1,52,52,53,-1,47,47,47,47,47,47,48,49,50,51,52,53,54,55,-1,59,59,59,59,59,-1,59,-1,-1,64,
45,45,45,45,45,45,45,45,46,47,48,49,49,48,47,47,47,-1,51,51,52,53,-1,48,48,48,48,48,48,48,49,-1,52,52,53,54,55,-1,58,58,59,60,60,-1,-1,-1,66,65,
46,46,46,46,46,-1,46,46,46,47,48,49,49,48,48,48,48,49,50,51,52,53,-1,49,49,49,49,49,49,49,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,
47,47,47,47,-1,-1,47,47,47,47,48,49,49,49,49,49,49,49,50,51,52,53,-1,-1,-1,50,-1,-1,50,50,50,50,51,52,53,54,55,-1,58,58,59,60,61,62,-1,65,65,66,
48,48,48,-1,-1,-1,-1,-1,48,48,48,49,-1,50,50,50,50,-1,-1,52,52,53,54,53,52,51,52,-1,-1,-1,-1,-1,-1,53,53,54,55,-1,59,59,59,60,61,-1,-1,66,66,66,
49,49,49,50,51,52,51,50,49,49,49,49,50,51,51,51,-1,-1,-1,-1,53,53,54,53,52,52,52,53,54,55,56,57,-1,54,54,54,55,-1,60,60,60,60,61,-1,-1,67,67,67,
1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,
1,1,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,-1,23,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,-1,43,43,44,45,46,
2,2,2,2,-1,5,-1,7,7,8,9,10,11,12,13,-1,-1,17,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,-1,-1,-1,-1,-1,45,45,46,
3,3,3,3,-1,-1,-1,-1,8,8,9,10,11,12,-1,-1,-1,18,18,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,-1,-1,45,45,46,
-1,4,4,4,5,-1,-1,-1,9,9,9,-1,-1,-1,-1,-1,-1,-1,-1,19,19,-1,-1,23,23,-1,-1,-1,-1,-1,-1,31,-1,33,33,34,35,36,37,38,39,40,41,42,43,44,45,46,
-1,5,5,5,5,6,7,8,9,10,10,11,12,13,-1,-1,-1,-1,-1,20,20,-1,-1,24,24,-1,37,36,35,34,33,32,-1,-1,-1,-1,36,-1,-1,-1,-1,-1,-1,43,43,44,45,46,
-1,6,6,6,6,6,7,8,9,10,11,11,12,13,14,15,16,17,18,19