// Arup Guha
// 5/13/2020
// Solution to 2020 Summer COP 3502 Program #2: Super Slow Supermarket

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

// Important constants in the assignment description.
#define MAXNAMESIZE 9
const int NUMLINES = 12;
const int MAXITEMS = 100;
const int TIMEPERITEM = 5;
const int TIMEPERCUSTOMER = 30;
const int MAXTIME = 2000000000;

// Stores info for one customer.
typedef struct customerNode {
    char name[MAXNAMESIZE+1];
    int timeInLine;
    int lineNum;
    int numItems;
} customerNode;

// Node for our linked lists of customers.
typedef struct llnode {
    customerNode* customerPtr;
    struct llnode* next;
} llnode;

// Struct to store our queue.
typedef struct queue {
    llnode* front;
    llnode* back;
} queue;

// Queue Functions.
void initQueue(queue* qPtr);
void enqueue(queue* qPtr, llnode* newNode);
int empty(queue* qPtr);
customerNode* frontCustomer(queue* qPtr);
llnode* dequeue(queue* qPtr);

// Functions that allocate and free memory.
customerNode* makeCustNode(char* name, int mytime, int myline, int numItems);
void freeNode(llnode* ptrNode);

// Functions that help us during the simulation.
int getNext(queue lines[], int curTime);
int timeUsed(customerNode* custPtr);

int main(void) {

    int numCases;
    scanf("%d", &numCases);

    // Process all cases.
    for (int loop=0; loop<numCases; loop++) {

        // Read in # of customers.
        int numCust;
        scanf("%d", &numCust);

        // Create the array for the lines.
        queue lines[NUMLINES];

        // Make each queue empty.
        for (int i=0; i<NUMLINES; i++)
            initQueue(&lines[i]);

        // Preload each line!
        for (int i=0; i<numCust; i++) {

            // Read this person's information.
            char name[MAXNAMESIZE+1];
            int mytime, myline, numItems;
            scanf("%d%d%s%d", &mytime, &myline, name, &numItems);

            // Create a struct to store it.
            customerNode* tmpPtr = makeCustNode(name, mytime, myline, numItems);

            // Create a linked list node with this info.
            llnode* tmpNode = malloc(sizeof(llnode));
            tmpNode->customerPtr = tmpPtr;
            tmpNode->next = NULL;

            // Add to back of the line!
            enqueue(&lines[myline-1], tmpNode);
        }

        // Will store what time it is now.
        int curTime = 0;

        // This actually works, since we know we'll have exactly 1 customer each time.
        for (int i=0; i<numCust; i++) {

            // This function does the heavy lifting - it figures out which line to take from.
            int whichLine = getNext(lines, curTime);

            // Dequeue this item from the appropriate queue.
            llnode* tmpNode = dequeue(&lines[whichLine]);

            // So we type less...
            customerNode* tmpPtr = tmpNode->customerPtr;

            // Update starting time, if necessary.
            if (curTime < tmpPtr->timeInLine)
                curTime = tmpPtr->timeInLine;

            // Now, process this customer.
            curTime += timeUsed(tmpPtr);

            // Print out the status.
            printf("%s from line %d checks out at time %d.\n", tmpPtr->name, tmpPtr->lineNum, curTime);

            // Now we are safe to free this memory.
            freeNode(tmpNode);
        }
    }

    return 0;
}

// Returns the amount of time in seconds the customer pointed to by custPtr
// will take to check out.
int timeUsed(customerNode* custPtr) {
    return TIMEPERCUSTOMER + custPtr->numItems*TIMEPERITEM;
}

// Initialize the queue pointed to by qPtr.
void initQueue(queue* qPtr) {
    qPtr->front = NULL;
    qPtr->back = NULL;
}

// Enqueues the llnode pointed to by newNode to the queue pointed to by qPtr.
void enqueue(queue* qPtr, llnode* newNode) {

    // Add to an empty queue. Both front and back have to be set.
    if (empty(qPtr)) {
        qPtr->front = newNode;
        qPtr->back = newNode;
    }

    // Link back to new node and move back.
    else {
        qPtr->back->next = newNode;
        qPtr->back = newNode;
    }
}

// Returns 1 iff the queue pointed to by qPtr is empty.
int empty(queue* qPtr) {
    return qPtr->front == NULL;
}

// Returns a pointer to the front customer pointed to by the queue pointed
// to by qPtr. Returns NULL if there is no customer.
customerNode* frontCustomer(queue* qPtr) {

    // To be safe.
    if (empty(qPtr)) return NULL;

    // This is the customerNode pointerwe want.
    return qPtr->front->customerPtr;
}

// Returns a pointer to the llnode that is at the front of the queue pointed
// to by qPtr. Returns NULL if the queue is empty.
llnode* dequeue(queue* qPtr) {

    // To be safe.
    if (empty(qPtr)) return NULL;

    // Store node to return.
    llnode* retVal = qPtr->front;

    // Advance front.
    qPtr->front = qPtr->front->next;

    // Special case, going from 1 to 0 items in the queue.
    if (qPtr->front == NULL)
        qPtr->back = NULL;

    // This is what we return.
    return retVal;
}

// Frees all dynamically associated memory with the struct pointed to by
// ptrNode (an llnode).
void freeNode(llnode* ptrNode) {
    free(ptrNode->customerPtr);
    free(ptrNode);
}

// Creates a customer node using the information passed to the function
// and returns a pointer to the struct dynamically allocated.
customerNode* makeCustNode(char* name, int mytime, int myline, int numItems) {
    customerNode* tmp = malloc(sizeof(customerNode));
    strcpy(tmp->name, name);
    tmp->timeInLine = mytime;
    tmp->lineNum = myline;
    tmp->numItems = numItems;
    return tmp;
}
// Pre-condition: lines store the NUMLINES queues at the store specified in the
//                assignment at or after curTime. Also, one of the lines must be non-empty.
// Post-condition: Returns the 0-based line that should be the next to be processed.
int getNext(queue lines[], int curTime) {

    // Store the line number in res.
    int res = -1, minItems = MAXITEMS+1;

    // First just look for active lines. (Go in order to break ties.)
    for (int i=0; i<NUMLINES; i++) {

        // This should be skipped.
        if (empty(&lines[i])) continue;

        // This is the person we are considering.
        customerNode* tmp = frontCustomer(&lines[i]);

        // In this pass, we skip these.
        if (tmp->timeInLine > curTime) continue;

        // Only improve if we lower minimum # of items.
        if (tmp->numItems < minItems) {
            res = i;
            minItems = tmp->numItems;
        }
    }

    // There's an active line so return it.
    if (res != -1) return res;

    int bestTime = MAXTIME + 1;

    // If we get here, then we just want the first active line. We are guaranteed that no two lines
    // will be active at the same time.
    for (int i=0; i<NUMLINES; i++) {

        // This should be skipped.
        if (empty(&lines[i])) continue;

        // This is the person we are considering.
        customerNode* tmp = frontCustomer(&lines[i]);

        // In this pass, we skip these.
        if (tmp->timeInLine < bestTime) {
            res = i;
            bestTime = tmp->timeInLine;
        }
    }

    // This must be our answer.
    return res;
}