// Arup Guha
// 3/20/2017
// Alternate Solution to 2017 UCF HS Contest Naughty or Nice
// Note: This only stores 3 things in my object instead of 4.

import java.util.*;

public class naughty2 {

	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, 1);

				// And when it ends, exclusive.
				int last = start + (maxNum-1)*period;
				list[2*i+1] = new event(last, 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<=2*n; i++) {

				// Process each house on this day.
				while (j < list.length && list[j].ID == 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/2)%k];
				}

				// Update if necessary.
				if (cur > max) {
					res = i/2;
					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 ID;
	public int skip;
	public int value;

	// Store on events in even ID, off events in odd ID to avoid sorting issues.
	public event(int h, int s, int v) {
		ID = v == 1 ? 2*h : 2*h+1;
		skip = s;
		value = v;
	}

	// This is the mod number for these sets of houses.
	public int mod() {
		return (ID/2)%skip;
	}

	public int compareTo(event other) {
		return this.ID - other.ID;
	}
}