// Arup Guha
// 3/20/2017
// Solution to 2017 UCF HS Contest Naughty or Nice
// Note: To speed this up, use BufferedReader...

import java.util.*;

public class naughty {

	public static int n;
	public static event[] list;

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int numCases = stdin.nextInt();

		// Process each case.
		for (int loop=1; loop<=numCases; loop++) {

			// Get houses and days.
			n = stdin.nextInt();
			int d = stdin.nextInt();
			list = new event[2*d];

			// Read in each event.
			for (int i=0; i<d; i++) {

				// Get data.
				int start = stdin.nextInt();
				int period = stdin.nextInt();
				int maxNum = stdin.nextInt();

				// This is when this one starts.
				list[2*i] = new event(start, period, start%period, 1);

				// And when it ends, exclusive.
				int last = start + (maxNum-1)*period + 1;
				list[2*i+1] = new event(Math.min(n+1,last), period, start%period, -1);
			}

			// Sort so we can sweep through this.
			Arrays.sort(list);

			// Store the # of intervals that are on. on[i][j] stores how many intervals
			// with skip of i for j%i are on.
			int[][] on = new int[11][11];

			int res = -1, max = 0, j = 0;

			// Sweep through the houses.
			for (int i=1; i<n+1; i++) {

				// Process each house on this day.
				while (j < list.length && list[j].house == i) {
					on[list[j].skip][list[j].mod] += list[j].value;
					j++;
				}

				// Count how many presents house i is getting.
				int cur = 0;
				for (int k=2; k<=10; k++) {
					cur += on[k][i%k];
				}

				// Update if necessary.
				if (cur > max) {
					res = i;
					max = cur;
				}
			}

			// Output result.
			System.out.println("House "+res+" should get the biggest and best gift next Christmas.");
		}
	}
}

class event implements Comparable<event> {

	public int house;
	public int skip;
	public int mod;
	public int value;

	public event(int h, int s, int m, int v) {
		house = h;
		skip = s;
		mod = m;
		value = v;
	}

	public int compareTo(event other) {
		if (this.house != other.house) return this.house - other.house;
		return this.value - other.value;
	}
}