#define READ_NUM_TEST_CASES  true
#define USE_FAST_IO          false

////////////////////////////////////////////////////////////////////////////////
// AMALGAMATE: "../include/template.hpp" BEGINS HERE
//
	
	
	#include <bits/stdc++.h>
	using namespace std;
	
	
	////////////////////////////////////////////////////////////////////////////////
	// AMALGAMATE: "../include/abbrevs.hpp" BEGINS HERE
	//
		
		#define UI unsigned int
		
		#define LL long long
		#define ULL unsigned long long
		
		#define PII pair<int,int>
		
		
		#define RI ri()
		#define RUI rui()
		
		#define RLL rll()
		#define RULL rull()
		
		#define RSTR rstr()
		
		
		
		#define FOR(i,n) for(int i=0; i<int(n); ++i)
		#define FO(i,a,b) for(int i=(a); i<int(b); ++i)
		#define OF(i,a,b) for(int i=(b)-1; i>=int(a); --i)
		
		
		
		#define MIN(a,b) ((a)<(b) ? (a) : (b))
		#define MAX(a,b) ((b)<(a) ? (a) : (b))
		
		#define REMIN(a,b) ((a) = min(a,b))
		#define REMAX(a,b) ((a) = max(a,b))
		
		#define ALL(c) (c).begin(),(c).end()
		
		#define SQR(x) ((x)*(x))
		
		
		
		bool is_pow(int x) {
			return (x&(x-1)) == 0;
		}
		
	
	//
	// AMALGAMATE: "../include/abbrevs.hpp" ENDS HERE
	////////////////////////////////////////////////////////////////////////////////
	
	
	#if USE_FAST_IO
		
		////////////////////////////////////////////////////////////////////////////////
		// AMALGAMATE: "../include/fast-io.hpp" BEGINS HERE
		//
			
			
			//#define FREAD  fread
			//#define FWRITE fwrite
			
			#define FREAD  fread_unlocked
			#define FWRITE fwrite_unlocked
			
			
			
			
			
			
			struct Buffer {
				FILE* const stream;
				const int buffer_size;
			
				uint8_t* const buff;
				int pos = 0;
			
				Buffer(FILE* a_stream, int a_buffer_size) :
						stream( a_stream ),
						buffer_size( a_buffer_size ),
						buff( new uint8_t[ buffer_size ] ) {
					setvbuf(stream, NULL, _IONBF, 0);
				}
			
				~Buffer() {
					delete[] buff;
				}
			};
			
			
			
			
			
			
			
			
			
			
			class In_Buffer : private Buffer {
			public:
				In_Buffer(FILE* a_stream, int a_buffer_size) : Buffer(a_stream, a_buffer_size) {
					FREAD(buff, 1, buffer_size, stream);
				}
			
			public:
				void prepare(int num_chars) {
					auto remaining = buffer_size - pos;
					if(remaining >= num_chars) return;
			
					assert(remaining >= 0); // prevent compiler warning
					memcpy(buff, buff+pos, remaining);
			
					int read = FREAD(buff+remaining, 1, pos, stream);
					int block_end = remaining + read;
					memset(buff + block_end, 0, buffer_size - block_end);
					pos = 0;
				}
			
			public:
				char get_unchecked() {
					return buff[ pos++ ];
				}
			};
			
			
			template<class INT>
			INT read_unsigned(In_Buffer& buff) {
				buff.prepare(25);
			
				char c = buff.get_unchecked();
				while(c < '-') c = buff.get_unchecked();
			
				INT r = 0;
			
				for(;;) {
					if(c < '0') return r;
					c -= '0';
					r = r*10 + c;
					c = buff.get_unchecked();
				}
			}
			
			
			template<class INT>
			INT read_signed(In_Buffer& buff) {
				buff.prepare(25);
			
				char c = buff.get_unchecked();
				while(c < '-') c = buff.get_unchecked();
			
				bool minus = false;
				if(c=='-') {
					c = buff.get_unchecked();
					minus = true;
				}
			
				INT r = 0;
			
				for(;;)
				{
					if(c < '0') return minus ? -r : r;
					r = r*10 + (c-'0');
					c = buff.get_unchecked();
				}
			}
			
			
			
			
			In_Buffer& operator>>( In_Buffer& buff, char& c) {
				buff.prepare(1);
				c = buff.get_unchecked();
				return buff;
			}
			
			
			
			In_Buffer& operator>>( In_Buffer& buff, UI& r) { r = read_unsigned<UI>(buff); return buff; }
			In_Buffer& operator>>( In_Buffer& buff, ULL& r) { r = read_unsigned<ULL>(buff); return buff; }
			
			In_Buffer& operator>>( In_Buffer& buff, int& r) { r = read_signed<int>(buff); return buff; }
			In_Buffer& operator>>( In_Buffer& buff, LL& r) { r = read_signed<LL>(buff); return buff; }
			
			In_Buffer& operator>>( In_Buffer& buff, string& r) {
				r.clear();
			
				char c = buff.get_unchecked();
				while(c <= ' ') c = buff.get_unchecked();
			
				do {
					r.push_back( c );
					c = buff.get_unchecked();
				} while(c > ' ');
			
				return buff;
			}
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			class Out_Buffer : private Buffer {
			public:
				Out_Buffer(FILE* a_stream, int a_buffer_size) : Buffer(a_stream, a_buffer_size) {}
			
				~Out_Buffer() {
					flush();
				}
			
			public:
				void prepare(int num_chars) {
					if(buffer_size - pos >= num_chars) return;
					flush();
				}
			
				void flush() {
					FWRITE(buff, 1, pos, stream);
					pos = 0;
				}
			
			public:
				void put_unchecked(const char& c) {
					buff[ pos++ ] = c;
				}
			
				void put_unchecked(const char* str, int len) {
					memcpy(buff+pos, str, len);
					pos += len;
				}
			};
			
			
			
			
			
			
			template<class INT>
			void write_signed(Out_Buffer& buff, const INT& i) {
				buff.prepare(25);
			
				if(i == 0) {
					buff.put_unchecked('0');
					return;
				}
			
				auto ci = i;
			
				if(ci < 0) {
					buff.put_unchecked('-');
					ci = -ci;
				}
			
				const int sz = 25;
				char temp[sz];
				int pos = sz;
			
				while(ci) {
					temp[ --pos ] = '0' + ci%10;
					ci/=10;
				}
			
				buff.put_unchecked(temp+pos, sz-pos);
			}
			
			
			
			template<class INT>
			void write_unsigned(Out_Buffer& buff, const INT& i) {
				buff.prepare(25);
			
				if(i==0) {
					buff.put_unchecked('0');
					return;
				}
			
				const int sz = 25;
				char temp[sz];
				int pos = sz;
			
				auto ci = i;
			
				while(ci) {
					temp[ --pos ] = '0' + ci%10;
					ci/=10;
				}
			
				buff.put_unchecked(temp+pos, sz-pos);
			}
			
			
			
			Out_Buffer& operator<<( Out_Buffer& buff, const char& c) {
				buff.prepare(1);
				buff.put_unchecked( c );
				return buff;
			}
			
			Out_Buffer& operator<<( Out_Buffer& buff, const UI& r) { write_unsigned<UI>(buff, r); return buff; }
			Out_Buffer& operator<<( Out_Buffer& buff, const ULL& r) { write_unsigned<ULL>(buff, r); return buff; }
			
			Out_Buffer& operator<<( Out_Buffer& buff, const int& r) { write_signed<int>(buff, r); return buff; }
			Out_Buffer& operator<<( Out_Buffer& buff, const LL& r) { write_signed<LL>(buff, r); return buff; }
			
			Out_Buffer& operator<<( Out_Buffer& buff, const char* cstr) { auto len = strlen(cstr); buff.prepare(len); buff.put_unchecked(cstr, len); return buff; }
			Out_Buffer& operator<<( Out_Buffer& buff, const string& str) { buff.prepare( str.size() ); buff.put_unchecked(str.data(), str.size()); return buff; }
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			#define BUFF_SIZE 32768
			In_Buffer  fast_cin(  stdin,  BUFF_SIZE );
			Out_Buffer fast_cout( stdout, BUFF_SIZE );
			//Out_Buffer fast_cerr( stderr, BUFF_SIZE );
			
			char fast_endl = '\n';
			
		
		//
		// AMALGAMATE: "../include/fast-io.hpp" ENDS HERE
		////////////////////////////////////////////////////////////////////////////////
		
		#define cin fast_cin
		#define cout fast_cout
		#define endl fast_endl
	#else
		
		////////////////////////////////////////////////////////////////////////////////
		// AMALGAMATE: "../include/slow-io.hpp" BEGINS HERE
		//
			
			struct Slow_IO_Singleton {
				Slow_IO_Singleton() {
					ios_base::sync_with_stdio( false );
			
					std::cin.tie( nullptr );
					std::cout.tie( nullptr );
			
					setlocale(LC_ALL,"C");
			
					const int buffer_size = 32768;
			
					static char stdin_buffer[ buffer_size ];
					static char stdout_buffer[ buffer_size ];
			
					cin.rdbuf()->pubsetbuf( stdin_buffer, buffer_size );
					cout.rdbuf()->pubsetbuf( stdout_buffer, buffer_size );
				}
			
				~Slow_IO_Singleton() {
			
				}
			};
			
			
			Slow_IO_Singleton slow_io_singleton;
			
		
		//
		// AMALGAMATE: "../include/slow-io.hpp" ENDS HERE
		////////////////////////////////////////////////////////////////////////////////
		
		#define endl '\n'
	#endif
	
	
	////////////////////////////////////////////////////////////////////////////////
	// AMALGAMATE: "../include/abbrevs-io.hpp" BEGINS HERE
	//
		
		
		
		
		int ri()   { int r; cin >> r; return r; }
		UI  rui()  { UI r; cin >> r; return r; }
		
		LL  rll()  { LL r;  cin >> r; return r; }
		ULL rull() { ULL r; cin >> r; return r; }
		
		string rstr() {string s; cin >> s; return s; }
		
	
	//
	// AMALGAMATE: "../include/abbrevs-io.hpp" ENDS HERE
	////////////////////////////////////////////////////////////////////////////////
	
	
	
	////////////////////////////////////////////////////////////////////////////////
	// AMALGAMATE: "../include/debug.hpp" BEGINS HERE
	//
		
		
		#define ASS(x) assert(x)
	
	//
	// AMALGAMATE: "../include/debug.hpp" ENDS HERE
	////////////////////////////////////////////////////////////////////////////////
	
	
	
	
	//
	// for salgo
	#define CONTEST_MODE
	
	namespace salgo {};
	using namespace salgo;
	//

//
// AMALGAMATE: "../include/template.hpp" ENDS HERE
////////////////////////////////////////////////////////////////////////////////


//#include <salgo/graph.hpp> // c++17
//#include <salgo/binomial.hpp>
//#include <salgo/modulo.hpp>
//#include <salgo/common.hpp>


#define FARMERS_MAX 38

const int RUN_AWAY = 10000;

//#define DEBUG
#define DEBUG_CASE 0

using F = char;


struct Vec {
	array<F,2> pos{};

	Vec() = default;
	Vec(const F& x, const F& y) : pos{{x,y}} {}

	F& operator[](int i) { return pos[i]; }
	const F& operator[](int i) const { return pos[i]; }

	Vec operator-() const {
		return Vec{(F)-pos[0], (F)-pos[1]};
	}
};


bool operator==(const Vec& a, const Vec& b) {
	return a.pos == b.pos;
}

bool operator!=(const Vec& a, const Vec& b) {
	return a.pos != b.pos;
}


Vec operator+(const Vec& a, const Vec& b) {
	return Vec(a[0] + b[0], a[1] + b[1]);
}

Vec operator-(const Vec& a, const Vec& b) {
	return Vec(a[0] - b[0], a[1] - b[1]);
}


ostream& operator<<(ostream& os, const Vec& vec) {
	os.precision(2);
	return os << "(" << (int)vec.pos[0] << ", " << (int)vec.pos[1] << ")";
}









int avg_moves_limit;
int N = 20;



inline bool check_bounds(Vec v) {
	if(v[0] < 0) return false;
	if(v[1] < 0) return false;
	if(v[0] >= N) return false;
	if(v[1] >= N) return false;
	return true;
}


enum Unit_Type {
	TYPE_FARMER,
	TYPE_TANK
};

namespace std{
	string to_string(Unit_Type type) {
		switch(type) {
			case TYPE_FARMER: return "FARMER";
			case TYPE_TANK:   return "TANK";
			default:          return "UNKNOWN_UNIT_TYPE";
		}
	}
}

struct Unit {
	Vec pos;
	bool can_move = true;
};

struct Farmer : Unit {
	int gold = 0;
};

struct Tank : Unit {
	bool stopped = false;
};





template<class T>
struct Array_2D : array<array<T,20>,20> {
	      T& operator()(Vec v)       { return (*this)[v[1]][v[0]]; }
	const T& operator()(Vec v) const { return (*this)[v[1]][v[0]]; }
};













struct Action;




short get_unit_code(Unit_Type type, int idx) {
	if(type == TYPE_FARMER) return idx+1;
	else return -idx-1;
}


struct State {
	vector<Farmer> farmers;
	vector<Tank> tanks;

	Unit& unit(Unit_Type type, int i) {
		if(type == TYPE_FARMER) return farmers[i];
		else return tanks[i];
	}

	const Unit& unit(Unit_Type type, int i) const {
		if(type == TYPE_FARMER) return farmers[i];
		else return tanks[i];
	}

	int num_units(Unit_Type type) const {
		if(type == TYPE_FARMER) return farmers.size();
		else return tanks.size();
	}


	double get_p() const {
		static double p = -1;
		if(p >= 0) return p;

		int num_rocks = 0;

		FOR(y,N) FOR(x,N) {
			Vec v = {(F)y,(F)x};
			if(rock(v)) ++num_rocks;
		}

		return p = 1.0 * num_rocks / (N*N);
	}


	Array_2D<short> gold{};
	Array_2D<short> rock{};
	Array_2D<short> has_unit{};

	int has_unit_of_type(Unit_Type type, Vec v) const {
		auto val = has_unit(v);

		if(type == TYPE_FARMER && val > 0) {
			return val-1;
		}

		if(type == TYPE_TANK && val < 0) {
			return -val - 1;
		}

		return -1;
	}

	int gold_at_base = 200;

	int turn_counter = 1;
	int commands_counter = 0;

	int total_gold_on_map = 0;
	int total_gold_at_farmers = 0;

	int total_rock_amount = 0;
	int total_rock_num = 0;


	void read_from_stdin() {
		N = RI;
		FOR(y,N) FOR(x,N) {
			auto val = RI;
			if(val > 0) {
				total_gold_on_map += val;
				gold[y][x] = val;
			}
			else if(val < 0) {
				val *= -1;
				rock[y][x] = val;
				total_rock_amount += val;
				total_rock_num++;
			}
		}
	}






	void destroy_gold(Vec v, int x) {
		assert(gold(v) >= x);
		gold(v) -= x;
		total_gold_on_map -= x;
	}

	void destroy_rock(Vec v, int x) {
		assert(rock(v) >= x);
		rock(v) -= x;
		total_rock_amount -= x;
		if(rock(v) == 0) total_rock_num--;
	}


	void create_unit(Unit_Type type) {
		assert(gold_at_base >= 100);
		gold_at_base -= 100;
		if(type == TYPE_FARMER) farmers.emplace_back();
		else tanks.emplace_back();
	}



	void dispatch(const Action& action);
};



const char RED[] = "\033[31m";
const char BG_RED[] = "\033[41m";

const char GREEN[] = "\033[32m";
const char BG_GREEN[] = "\033[42m";

const char BLUE[] = "\033[34m";
const char BG_BLUE[] = "\033[44m";

const char YELLOW[] = "\033[33m";
const char BG_YELLOW[] = "\033[43m";

const char RESET[] = "\033[0m";

ostream& operator<<(ostream& os, const State& state) {
	FOR(y,N) {
		FOR(x,N) {
			Vec pos(x,y);
			if(state.gold(pos)) os << GREEN;
			if(state.rock(pos)) os << RED;

			if(state.has_unit_of_type(TYPE_FARMER, pos) != -1) os << BG_YELLOW;
			if(state.has_unit_of_type(TYPE_TANK,   pos) != -1) os << BG_BLUE;

			int val = max(state.gold(pos), state.rock(pos));
			if(val) os << 10 * val / 513;
			else os << ' ';
			os << RESET;
		}
		os << endl;
	}
	os << "GOLD: " << state.gold_at_base << "   "
		<< "GOLD-AT-FARMERS: " << state.total_gold_at_farmers << "   "
		<< "GOLD-ON-MAP: " << state.total_gold_on_map << "   "
		<< "TOTAL-TURNS: " << state.turn_counter << "   "
		<< "TOTAL-COMMANDS: " << state.commands_counter << endl;
	return os;
}
















enum class Action_Type {
	BUILD,
	MOVE,
	STOP_TANK,
	END_TURN
};

struct Range {
	Vec fr,to;
};

ostream& operator<<(ostream& os, const Range& range) {
	return os << range.fr << "->" << range.to;
}


struct Action {
	Action_Type type;
	Unit_Type unit_type;
	int unit_index;
	Vec dir;
	
	Range range(const State& state) const {
		Range r;
		r.fr = state.unit(unit_type, unit_index).pos;
		r.to = r.fr + dir;
		return r;
	}

	string to_command(const State& state) const {
		switch(type) {
			case Action_Type::BUILD:
				return "R " + ::std::to_string(unit_type);
				break;

			case Action_Type::MOVE: {
				auto r = range(state);
				ostringstream os;
				os << "M " << (int)r.fr[1] << " " << (int)r.fr[0] << " " << (int)r.to[1] << " " << (int)r.to[0];
				return os.str();
				break;
			}

			case Action_Type::END_TURN:
				return "=";
				break;

			default:
				return "";
				break;
		}
	}

	string to_string(const State& state) const {
		ostringstream os;
		switch(type) {
			case Action_Type::BUILD:
				os << "BUILD " << ::to_string(unit_type);
				break;

			case Action_Type::MOVE: {
				auto r = range(state);
				os << "MOVE " << ::to_string(unit_type) << "[" << unit_index << "] " << r;
				break;
			}

			case Action_Type::STOP_TANK: {
				auto r = range(state);
				os << "STOP TANK[" << unit_index << "] @ " << r.fr;
				break;
			}

			case Action_Type::END_TURN:
				os << "END_TURN";
				break;
		}
		return os.str();
	}
};





















void State::dispatch(const Action& action) {
	++commands_counter;

	switch(action.type) {
		case Action_Type::BUILD:
			assert( !has_unit({0,0}) );
			has_unit({0,0}) = get_unit_code(action.unit_type, num_units(action.unit_type));
			create_unit( action.unit_type );
			break;

		case Action_Type::MOVE: {
			auto range = action.range(*this);
			assert(check_bounds(range.fr));
			assert(check_bounds(range.to));
			if(action.unit_type == TYPE_TANK) {
				assert( tanks[action.unit_index].stopped == false );
			}
			else {
				// TYPE_FARMER
				assert( "travelling farmer onto rock" && rock(range.to) == 0 );
			}
			assert( unit( action.unit_type, action.unit_index ).can_move );
			unit( action.unit_type, action.unit_index ).can_move = false;
			auto unit_code = get_unit_code(action.unit_type, action.unit_index);
			assert( has_unit(range.fr) == unit_code);
			assert(!has_unit(range.to));
			has_unit(range.fr) = 0;
			has_unit(range.to) = unit_code;
			unit( action.unit_type, action.unit_index ).pos = range.to;
			break;
		}


		case Action_Type::STOP_TANK:
			assert( action.unit_type == TYPE_TANK );

			assert( tanks[ action.unit_index ].stopped == false );
			tanks[ action.unit_index ].stopped = true;
			break;


		case Action_Type::END_TURN:
			++turn_counter;

			// collect gold
			FOR(i, num_units(TYPE_FARMER)) {
				auto& farmer = farmers[i];
				int amount = min(10, (int)gold(farmer.pos));
				destroy_gold(farmer.pos, amount);
				farmer.gold += amount;
				total_gold_at_farmers += amount;
			}

			// destroy rock
			FOR(i, num_units(TYPE_TANK)) {
				auto& tank = tanks[i];
				int amount = min(10, (int)rock(tank.pos));
				destroy_rock(tank.pos, amount);
			}

			// gold to base
			int i_farmer = has_unit_of_type(TYPE_FARMER, Vec{0,0});
			if(i_farmer >= 0) {
				gold_at_base += farmers[i_farmer].gold;
				total_gold_at_farmers -= farmers[i_farmer].gold;
				farmers[i_farmer].gold = 0;
			}

			FOR(type,2) FOR(i, num_units((Unit_Type)type)) unit((Unit_Type)type, i).can_move = true;
			break;
	}
}

























const array<Vec,4> dirs = {{
	{1,0}, {-1,0}, {0,1}, {0,-1}
}};

const array<Vec,5> dirs_or_still = {{
	{0, 0},
	{1,0}, {-1,0}, {0,1}, {0,-1}
}};


double cost(const State& state, Vec v) {
	return (state.rock(v) + 9) / 10  +  0.3346 * v[0]/40 + 0.8346 * v[1]/40;
}



struct Dijkstra_Result {
	Array_2D<double> dists;
	int total_objects_amount = 0;
	int total_objects_num = 0;
};


Dijkstra_Result dij(const State& state, Unit_Type dij_type, const vector<Vec>& start_from = {Vec{0,0}}) {
	Dijkstra_Result res;

	Array_2D<double> d;

	FOR(y,N) FOR(x,N) d[y][x] = DBL_MAX;

	struct Node {
		double dist;
		Vec what;

		bool operator<(const Node& o) const { return dist > o.dist; }
	};
	
	priority_queue<Node> pq;

	for(auto& v : start_from) {
		d(v) = 0;
		pq.emplace(Node{0, v});
	}

	//int gold_reached = 0;

	while(pq.size()) {
		auto node = pq.top();
		pq.pop();

		double cdist = node.dist;
		Vec cpos = node.what;

		if(d(cpos) != cdist) continue;

		if(dij_type == TYPE_FARMER  &&  state.gold(cpos)) {
			++res.total_objects_num;
			res.total_objects_amount += state.gold(cpos);
		}
		if(dij_type == TYPE_TANK  &&  state.rock(cpos)) {
			++res.total_objects_num;
			res.total_objects_amount += state.rock(cpos);
		}


		for(auto dir : dirs) {
			auto dest_pos = cpos + dir;
			if(!check_bounds(dest_pos)) continue;

			if(dij_type == TYPE_FARMER  &&  state.rock(dest_pos) > 0) continue;

			double cand = cdist + 1 + cost(state, dest_pos); //cost_cpos;

			if(cand < d(dest_pos)) {
				d(dest_pos) = cand;
				pq.emplace(Node{cand, dest_pos});
			}
		}
	}

	res.dists = std::move(d);
	return res;
}



vector<int> random_order(int n) {
	vector<int> v(n);
	FOR(i,n) v[i] = i;
	random_shuffle(ALL(v));
	return v;
}


vector<Action> heura(const State& state) {
	vector<Action> actions;

	Array_2D<bool> used_dests{};
	Array_2D<bool> freed_dests{};

	vector<char> farmer_moved(state.farmers.size());
	vector<char> tank_moved(state.farmers.size());

	auto find_farmers = dij(state, TYPE_FARMER);

	vector<Vec> hidden_gold;
	hidden_gold.reserve(N*N);
	FOR(y,N) FOR(x,N) {
		Vec v(x,y);
		if(find_farmers.dists(v) == DBL_MAX && state.gold(v)) hidden_gold.emplace_back(v);
	}

	//if(hidden_gold.size()) cerr << "example hidden gold: " << hidden_gold[0] << endl;

	Dijkstra_Result farmers_sink;
	Dijkstra_Result tanks_sink;


	if(state.total_gold_on_map > 0) {
		vector<Vec> free_gold;
		free_gold.reserve(N*N);
		FOR(y,N) FOR(x,N) {
			Vec p(x,y);
			if(find_farmers.dists(p) < DBL_MAX && !state.has_unit(p) && state.gold(p)) free_gold.push_back(p);
		}
		farmers_sink = dij(state, TYPE_FARMER, free_gold); // compute distances from gold
	}
	else {
		farmers_sink = find_farmers;
	}



	//FOR(y,N) FOR(x,N) assert(used_dests[y][x] == false);


		vector<Vec> rocks;
	if(hidden_gold.empty()) {
		//cerr << "all gold accessible - tanks now randomly destroy rocks" << endl;

		FOR(y,N) FOR(x,N) {
			Vec v(x,y);
			if(state.rock(v) && !state.has_unit(v)) rocks.emplace_back(v);
		}
	}





	if(state.total_rock_amount == 0) {
		//cerr << "no rocks left" << endl;
		vector<Vec> farmers_list;
		for(auto& f : state.farmers) farmers_list.push_back(f.pos);

		tanks_sink = dij(state, TYPE_TANK, farmers_list);
	}
	else if(hidden_gold.empty()) {
		tanks_sink = dij(state, TYPE_TANK, rocks);
	}
	else {
		tanks_sink = dij(state, TYPE_TANK, hidden_gold); // compute distances from hidden gold
	}



	






	




	// move tanks forward somewhere (unless they're already on some rock)

	bool random_walk = state.total_rock_amount == 0;
	random_walk = false;
	random_walk = rand() < 0.15 * RAND_MAX;

	FOR(t, state.tanks.size()) {
		auto& tank = state.tanks[t];
		if(!tank.can_move) continue;
		if(tank.stopped) continue;

		if(state.rock(tank.pos)) continue;

		double best_dist = DBL_MAX;
		Vec best_dist_where;

		for(auto& dir : dirs) {
			auto dest = tank.pos + dir;
			if(!check_bounds(dest)) continue;

			if(used_dests(dest)) continue;
			if(state.has_unit(dest) && !freed_dests(dest)) continue;

			auto dist_there = tanks_sink.dists(dest);
			if(state.total_rock_amount == 0) dist_there *= -1;

			if(state.total_rock_amount == 0 && state.gold(dest)) continue;

			if(random_walk || dist_there < best_dist) {
				if(!random_walk || rand()%4 == 0) {
					best_dist = dist_there;
					best_dist_where = dir;
				}
			}
		}

		auto dest = tank.pos + best_dist_where;

		if((best_dist < DBL_MAX || random_walk)  &&  !used_dests(dest) && best_dist_where != Vec{0,0}) {
			// move!
			Action a;
			a.type = Action_Type::MOVE;
			a.unit_type = TYPE_TANK;
			a.unit_index = t;
			a.dir = best_dist_where;
			actions.emplace_back( std::move(a) );
			used_dests(dest) = true;
			freed_dests(tank.pos) = true;
			//cerr << "tank at " << tank.pos << " travelling downwards to sink" << endl;
		}
	}










	// pick one farmer that will go back with gold
	int giver = -1;
	double min_dist = DBL_MAX;
	if(N>3) FOR(t, state.farmers.size()) {
		auto& farmer = state.farmers[t];
		if(!farmer.can_move) continue;

		if(state.gold(farmer.pos) && farmer.pos[0] + farmer.pos[1] > 2 && (state.tanks.size() || (int)state.farmers.size() >= 10)) continue;

		if(farmer.gold == 0) continue;
		if(farmer.gold + state.gold_at_base < 100) continue;

		double dist_to_base = find_farmers.dists(farmer.pos);

		if(dist_to_base < min_dist) {
			min_dist = dist_to_base;
			giver = t;
		}
	}

	if(giver != -1) {
		//cerr << "farmer at " << state.farmers[giver].pos << " going back to base" << endl;
	}

	if(giver >= 0  &&  state.farmers[giver].can_move) {
		auto& farmer = state.farmers[giver];

		double best_dist = DBL_MAX;
		Vec best_dir = {0,0};

		for(auto& dir : dirs) {
			auto dest = farmer.pos + dir;
			if(!check_bounds(dest)) continue;

			if(state.rock(dest)) continue;

			if(used_dests(dest)) continue;

			if(state.has_unit(dest) && !freed_dests(dest)) continue;

			double cand = find_farmers.dists(dest);
			if(cand < best_dist) {
				best_dist = cand;
				best_dir = dir;
			}
		}

		if(best_dir != Vec{0,0}) {
			Action a;
			a.type = Action_Type::MOVE;
			a.unit_type = TYPE_FARMER;
			a.unit_index = giver;
			a.dir = best_dir;
			actions.emplace_back( std::move(a) );
			used_dests(farmer.pos + a.dir) = true;
			freed_dests(farmer.pos) = true;
		}
	}











	


	bool all_gold_covered = true;
	
	FOR(y,N) FOR(x,N) {
		Vec v = {(F)x,(F)y};
		if(state.gold(v) && state.has_unit_of_type(TYPE_FARMER, v) == -1) all_gold_covered = false;
	}
	



	int num_to_base = 0;

	// any farmers not assigned yet? just move them forward somewhere (unless they're already on some gold)
	int iters = state.total_gold_on_map == 0 ? 200 : 1;
	FOR(iter,iters)
	FOR(t, state.farmers.size()) {
		auto& farmer = state.farmers[t];
		if(!farmer.can_move) continue;
		if(farmer_moved[t]) continue;

		if(t == giver) continue;

		//if(state.gold(farmer.pos)) continue; // already on some gold

		bool to_base = all_gold_covered && state.gold(farmer.pos) == 0 && farmer.gold > 0 && farmer.pos[0] > (int)state.farmers.size() * state.total_gold_on_map / RUN_AWAY;
		if(to_base) ++num_to_base;

		bool away_from_base = state.total_gold_on_map < 1000 && farmer.gold == 0;

		bool swap_dir = rand() < 0.1 * RAND_MAX;

		if(state.tanks.empty()) swap_dir = rand() < 0.04 * RAND_MAX;
		else if(state.get_p() < 0.35) swap_dir = rand() < 0.5 * RAND_MAX;

		if(state.tanks.empty() && state.total_gold_on_map == 0 && farmer.gold == 0) swap_dir = rand() < 0.1 * RAND_MAX;

		//Vec blacklist_dir = {0,0};
		//if(state.tanks.empty() && state.total_gold_on_map > 0) {
		//	blacklist_dir = rand()%2 ? Vec{1,0} : Vec{0,1};
		//}


		double best_dist = DBL_MAX;
		Vec best_dist_where;

		bool force = false;
		Vec forced_dir = {0,0};

		// force up, then left
		if(N > 3 && (state.tanks.empty() || state.total_rock_amount == 0) && to_base) {
			force = true;
			if(farmer.pos[1] > 0) forced_dir = {0,-1};
			else forced_dir = {-1,0};
		}


		for(auto& dir : dirs) {
			auto dest = farmer.pos + dir;
			if(!check_bounds(dest)) continue;

			if(force && dir != forced_dir) continue;

			//if(dir == blacklist_dir) continue;

			if(used_dests(dest)) continue;
			if(state.rock(dest)) continue;
			if(state.has_unit(dest) && !freed_dests(dest)) continue;

			
			if(state.tanks.empty() && state.gold(farmer.pos) && (dir[0] > 0 || dir[1] > 0) &&
					state.gold(dest) && check_bounds(farmer.pos - dir) && state.has_unit_of_type(TYPE_FARMER, farmer.pos - dir) >= 0 && !state.gold(farmer.pos - dir)) {

				//cerr << "                       MOVE AWAY" << endl;
				best_dist = -69;
				best_dist_where = dir;
				break;
			}
			

			// force down
			if(N > 3 && (state.tanks.empty() || state.total_rock_amount == 0) && away_from_base && dir == Vec{0,1}) {
				best_dist = 0;
				best_dist_where = dir;
				break;
			}

			auto dist_there = farmers_sink.dists(dest);

			if(swap_dir || dist_there < best_dist) {

				if(!swap_dir || rand()%4 == 0) {
					best_dist = dist_there;
					best_dist_where = dir;
				}
			}
		}

		auto dest = farmer.pos + best_dist_where;

		if(best_dist == -69 || !state.gold(farmer.pos)) {

			if(best_dist < DBL_MAX  &&  !used_dests(dest)  &&  (N>3 || farmer.pos[0] == 0 || farmer.gold > 0)) {
				// move!
				Action a;
				a.type = Action_Type::MOVE;
				a.unit_type = TYPE_FARMER;
				a.unit_index = t;
				a.dir = best_dist_where;
				actions.emplace_back( std::move(a) );
				used_dests(dest) = true;
				freed_dests(farmer.pos) = true;
				farmer_moved[t] = true;
				//cerr << "farmer at " << farmer.pos << " travelling downwards to the sink" << endl;
			}
		}
	}

	//cerr << "number of farmers already returning to base: " << num_to_base << endl;






	if(state.gold_at_base >= 100  &&  !used_dests({0,0})  &&  !state.has_unit({0,0})) {
		bool prefer_farmers = state.tanks.size() > state.farmers.size();

		if(state.farmers.size() > 0 && state.tanks.size() > 0) {
			double ratio = 1.0 * state.farmers.size() / state.tanks.size();
			double want_ratio = 1.0 * find_farmers.total_objects_amount / state.total_rock_amount;

			prefer_farmers = ratio < want_ratio;
		}

		int max_farmers = 8;

		if(state.total_rock_amount == 0) max_farmers = FARMERS_MAX;

		if(state.get_p() < 0.35 && state.get_p() > 0.25) max_farmers = 10;

		int max_tanks = 25;

		if(state.get_p() < 0.35 && state.get_p() > 0.25) max_tanks = 10;

		if(state.total_rock_num > 200) max_farmers = 1;

		if(state.total_rock_amount == 0) prefer_farmers = true;

		if(N == 3 && find_farmers.total_objects_amount == state.total_gold_on_map) prefer_farmers = true;

		if(N == 3) max_farmers = 2;

		if(prefer_farmers && (int)state.farmers.size() < max_farmers && (find_farmers.total_objects_amount >= 100 || N == 3)) {
			Action a;
			a.type = Action_Type::BUILD;
			a.unit_type = TYPE_FARMER;
			actions.emplace_back( std::move(a) );
			used_dests({0,0}) = true;
		}
		else if((int)state.tanks.size() < max_tanks && state.total_rock_amount && ((int)state.farmers.size() || state.gold_at_base >= 200)) {
			Action a;
			a.type = Action_Type::BUILD;
			a.unit_type = TYPE_TANK;
			actions.emplace_back( std::move(a) );
			used_dests({0,0}) = true;
		}
	}

	if(actions.empty()) {
		Action a;
		a.type = Action_Type::END_TURN;
		actions.emplace_back( std::move(a) );
	}

	return actions;
}




void pause() {
	cin.ignore(1024000, '\n');
	cout << "Press enter to continue..." << endl;
	cout << endl;
	cout << endl;
	cout << endl;
	cout << endl;
	cout << endl;
	string s;
	getline(cin, s);
}


int total_turns = 0;

vector<int> turns_per_try;

struct Test_Case {

	void solve() {
		State state;
		state.read_from_stdin();

		while(state.total_gold_at_farmers + state.total_gold_on_map > 0) {
			auto actions = heura(state);
			for(auto& action : actions) {

				// debug
				//cerr << endl;
				//cerr << action.to_string(state) << endl;

				auto command = action.to_command(state);

				state.dispatch(action);
				if(command != "") cout << command << endl;
			}

			// debug
			#ifdef DEBUG
				if(DEBUG_CASE >= 0 && icase >= DEBUG_CASE) {
					cerr << state;
					pause();
				}
			#endif
		}

		cerr << "total turns: " << state.turn_counter << endl;
		cerr << "total commands: " << state.commands_counter << endl;

		total_turns += state.turn_counter;

		turns_per_try[icase] = state.turn_counter;

		cout << "===" << endl;
	}

	int icase = -1;
}; // struct Test_Case






int main() {
	int num_cases = READ_NUM_TEST_CASES ? RI : 1;
	avg_moves_limit = RI;

	turns_per_try.resize(num_cases);
	
	FOR(i, num_cases) {
		Test_Case tc;
		tc.icase = i;
		tc.solve();

		#ifdef DEBUG
		if(DEBUG_CASE >= 0 && i>=DEBUG_CASE) break;
		#endif
	}

	cerr << endl << "SUMMARY:" << endl;
	FOR(i,num_cases) {
		cerr << "try " << i << ": " << turns_per_try[i] << endl;
	}
	cerr << endl;

	double avg_turns = 1.0 * total_turns / num_cases;
	cerr << "avg turns: " << avg_turns << endl;
	if(avg_turns > avg_moves_limit) {
		cerr << "ERROR" << endl;
		return 1;
	}

	return 0;
}