void swap(void **x, void **y) {
	void *t = *x;
	*x = *y;
	*y = t;
}

/* 
 * Solution for the "Interpreter" problem.
 * UVa ID: 10033
 */
#include <stdio.h>

#define MAX_REG 10
#define MAX_RAM 1000

int pointer;
int regArray[MAX_REG];
int ram[MAX_RAM];

/* initialize registers and ram */
int init() {
	int i;
	for (i = 0; i < MAX_REG; i++) {
		regArray[i] = 0;
	}
	for (i = 0; i < MAX_RAM; i++) {
		ram[i] = 0;
	}
	
}

/* decode instruction */
int decode() {
	int command, a1, a2;
	command = ram[pointer] / 100;
	a1 = (ram[pointer] % 100) / 10;
	a2 = ram[pointer] % 10;
	
	switch (command) {
		/* halt */
		case 1 :		
			return 0;
			break;
			
		/* set register a1 to a2 */
		case 2 :
			regArray[a1] = a2;
			pointer++;
			break;
			
		/* add a2 to register a1 */
		case 3 :
			regArray[a1] = (regArray[a1] + a2) % 1000;
			pointer++;
			break;
			
		/* multiply register a1 by a2 */
		case 4 :
			regArray[a1] = (regArray[a1] * a2) % 1000;
			pointer++;
			break;
			
		/* set register a1 to the value of register a2 */
		case 5 : 
			regArray[a1] = regArray[a2];
			pointer++;
			break;
			
		/* add the value of register a2 to register a1 */
		case 6 : 
			regArray[a1] = (regArray[a1] + regArray[a2]) % 1000;
			pointer++;
			break;
			
		/* multiply register a1 by the value of register a2 */
		case 7 :
			regArray[a1] = (regArray[a1] * regArray[a2]) % 1000;
			pointer++;
			break;
			
		/* set register a1 to the value in RAM whose address is in register a2 */
		case 8 :
			regArray[a1] = ram[regArray[a2]];
			pointer++;
			break;			
			
		/* set the value in RAM whose address in in register a2 to that of register a1 */
		case 9 :
			ram[regArray[a2]] = regArray[a1];
			pointer++;
			break;			
			
		/* goto */		
		case 0 :
			if (regArray[a2] != 0) {
				pointer = regArray[a1];
			} else {
				pointer++;
			}
			break;			
			
		default: 
			break;
	}
	return 1;	
}

/* main */
int main (int argc, const char * argv[]) {
	int i, j, cases, num_instr;
	char instr[5];

	scanf("%d", &cases);
	fgets(instr, sizeof(instr), stdin);
	fgets(instr, sizeof(instr), stdin);
	num_instr = 0;
	
	/* for the number of test cases specified */
	for (i = 0; i < cases; i++) {
		init();
		
		pointer = 0;
		
		if (i != 0) {
			printf("\n");
		}
		
		/* read input ram */
		while(fgets(instr, sizeof(instr), stdin) != NULL) {
			if (instr[0] == '\n') {
				break;
			}
			ram[pointer] = (instr[0] - '0') * 100 + (instr[1] - '0') * 10 + (instr[2] - '0');
			pointer++;
		}
		
		/* decode and interpret instructions until halt */
		num_instr = 1;
		pointer = 0;
		while (decode()) {
			num_instr++;
		}	
		
		printf("%d\n",num_instr);	
	}
	
	return 0;
}

/* 
 * Solution for the "Graphical Editor" problem.
 * UVa ID: 10267
 */
#include <stdio.h>

#define MAX 250
#define OFFSET 1
#define DOS_NAME 12

/* global image bounds */
int n, m;

/* fills a rectangle with the specified color */
int fillRectangle(int m_ini, int n_ini, int m_end, int n_end, char color, char pTable[][MAX+OFFSET]) {
	int i, j;
	for (i = n_ini; i <= n_end; i++) {
		for (j = m_ini; j <= m_end; j++) {
			pTable[i][j] = color;
		}
	}
	return 0;
}

/* fills a region R with the specified color */
int fillRegion(int x, int y, char oldColor, char newColor, char pTable[][MAX+OFFSET]) {	
	/* (x,y) is in region R */
	pTable[y][x] = newColor;
	
	/* recursively check all 4 directions for neighbours of (x,y) with same color */
	if ((pTable[y][x-1] == oldColor) && (x > OFFSET)) {         
		fillRegion(x-1, y, oldColor, newColor, pTable);
	}
	if ((pTable[y][x+1] == oldColor) && (x < m)) {       
		fillRegion(x+1, y, oldColor, newColor, pTable);
	}
	if ((pTable[y-1][x] == oldColor) && (y > OFFSET)) {        
		fillRegion(x, y-1, oldColor, newColor, pTable);
	}
	if ((pTable[y+1][x] == oldColor) && (y < n)) {        
		fillRegion(x, y+1, oldColor, newColor, pTable);
	}
	return 0;
}

/* outputs the image */
int printImage(int m, int n, char pTable[][MAX+OFFSET]) {
	int i, j;	
	for (i = OFFSET; i < n+OFFSET; i++) {
		for (j = OFFSET; j < m+OFFSET; j++ ) {
			printf("%c", pTable[i][j]);
		}
		printf("\n");
	}
	return 0;
}

/* main */
int main (int argc, const char * argv[]) {
	/* the image */
	char image[MAX+OFFSET][MAX+OFFSET];

	/* editor command */
	char command;
	
	/* coords */
	int x1, x2, y1, y2, tmp;
	
	/* colors */
	char color, oldColor;
	
	/* filename */
	char filename[DOS_NAME+1];
			
	while(scanf("%c", &command) != EOF) {		
		/* X, terminates the session */
		if (command == 'X') {
			return 0;
		}		
		switch (command) {
			/* create image */
			case 'I' :
				scanf("%d %d", &m, &n);
				fillRectangle(1, 1, m, n, 'O', image);
				break;
			
			/* clear image */
			case 'C' :
				fillRectangle(1, 1, m, n, 'O', image);
				break;
			
			/* colors a pixel */
			case 'L' :
				scanf("%d %d %c", &x1, &y1, &color);
				image[y1][x1] = color;
				break;
			
			/* draw vertical segment */
			case 'V' :
				scanf("%d %d %d %c", &x1, &y1, &y2, &color);
				if (y2 >= y1)
					fillRectangle(x1, y1, x1, y2, color, image);
				else
					fillRectangle(x1, y2, x1, y1, color, image);
				break;
			
			/* draw horizontal segment */
			case 'H' : 
				scanf("%d %d %d %c", &x1, &x2, &y1, &color);
				if (x2 >= x1)
					fillRectangle(x1, y1, x2, y1, color, image);
				else
					fillRectangle(x2, y1, x1, y1, color, image);
				break;
			
			/* draw rectangle */
			case 'K' : 
				scanf("%d %d %d %d %c", &x1, &y1, &x2, &y2, &color);
				if (x1 >= x2) {
					tmp = x1;
					x1 = x2;
					x2 = tmp;
				}
				if (y1 >= y2) {
					tmp = y1;
					y1 = y2;
					y2 = tmp;
				}
				fillRectangle(x1, y1, x2, y2, color, image);
				break;
			
			/* fill */
			case 'F' :
				scanf("%d %d %c", &x1, &y1, &color);
				oldColor = image[y1][x1];
				if (oldColor != color) {
					fillRegion(x1, y1, oldColor, color, image);
				}
				break;

			/* fill */
			case 'S' :
				scanf("%s", &filename);
				printf("%s\n", filename);
				printImage(m, n, image);
				break;			
		
			default: 
				break;
		}		
	}
	
	return 0;
}

/* 
 * Solution for the "LCD Display" problem.
 * UVa ID: 706
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_SIZE 9

int main (int argc, const char * argv[]) {
	/* number of vertical or horizontal segments in each digit */
	int s;
	
	/* the number to print */
	char digitString[MAX_SIZE];
	
	/* 
	 * LED representation for each number, according to 
	 * the following convention:
	 *
	 *  -0-
	 * |   |
	 * 2   1
	 * |   |
	 *  -3-
	 * |   |
	 * 5   4
	 * |   |
	 *  -6-
	 *
	 */
	
	const char conversionTable[10][7] = {
		      /* 0   1   2   3   4   5   6 */
		/* 0 */ '-','|','|',' ','|','|','-',	  
		/* 1 */ ' ','|',' ',' ','|',' ',' ',
		/* 2 */ '-','|',' ','-',' ','|','-',
		/* 3 */ '-','|',' ','-','|',' ','-',
		/* 4 */ ' ','|','|','-','|',' ',' ',
		/* 5 */ '-',' ','|','-','|',' ','-',
		/* 6 */ '-',' ','|','-','|','|','-',
		/* 7 */ '-','|',' ',' ','|',' ',' ',
		/* 8 */ '-','|','|','-','|','|','-',
		/* 9 */ '-','|','|','-','|',' ','-',

	};
	
	/* iterators */
	int i, j, k;
	
	while(scanf("%d %s", &s, &digitString) != EOF) {
		
		/* 0, ends the program */
		if (!s) {
			return 0;
		}
		
		int n = strlen(digitString);
		int digit;
		
		for (i = 0; i < 2*s+3; i++) {					
			for (j = 0; j < n; j ++) { 
						
				digit = digitString[j] - '0';

				/* upper, middle and lower parts */
				if ((i % (s + 1)) == 0) {
					printf(" ");
					for (k = 0; k < s; k++) {
						printf("%c", conversionTable[digit][(i / (s + 1)) * 3]);
					}
					printf(" ");
				}
				
				/* between upper and middle parts */
				if (i > 0 && i < (s + 1)) {
					printf("%c", conversionTable[digit][2]);
					for (k = 0; k < s; k++) {
						printf(" ");
					}
					printf("%c", conversionTable[digit][1]);
				}

				
				/* between middle and lower parts */
				if (i > (s + 1) && i < (2*s + 2)) {
					printf("%c", conversionTable[digit][5]);
					for (k = 0; k < s; k++) {
						printf(" ");
					}
					printf("%c", conversionTable[digit][4]);
				}
				
				/* if not the last number */
				if (j != n-1)
					printf(" ");
	
			}			
			printf("\n");
			
		}
		printf("\n");
		
	}
	
	return 0;
}

/* 
 * A solution for "The Trip" problem.
 * UVa ID: 10137
 */
#include <stdio.h>

int main (int argc, const char * argv[]) {
	/* number of students in the trip */
	long numOfStudents;
	
	/* the total sum of money spent */
	double total;
	
	/* the total amount of money to exchange in order to equalize */
	double exchange;
	
	/* the equalized trip amount to be payed by each student */
	double equalizedAmount;
	
	/* difference between the equalized amount and the amount spent */
	double diff;
	
	/* sum of all negative differences */
	double negativeSum;
	
	/* sum of all positive differences */
	double positiveSum;
	
	/* iterator */
	int i;
	
	while(scanf("%ld", &numOfStudents) != EOF) {
				
		/* 0, ends the program */
		if (!numOfStudents) {
			return 0;
		}
		
		/* keeps the amount of money spent by each student */
		double amountSpent[numOfStudents];		
		
		/* clean */
		total = 0;
		negativeSum = 0;
		positiveSum = 0;
				
		for (i = 0; i < numOfStudents; i++) {
			scanf("%lf\n", &amountSpent[i]);
			total += amountSpent[i];
		}
				
		equalizedAmount = total / numOfStudents;
		
		for (i = 0; i < numOfStudents; i++) {
			/* to ensure 0.01 precision */
			diff = (double) (long) ((amountSpent[i] - equalizedAmount) * 100.0) / 100.0;
			
			if (diff < 0) {
				negativeSum += diff;
			} else { 
				positiveSum += diff;
			}
		}

		/* when the total amount is even, these sums do not differ. otherwise, they differ in one cent */
		exchange = (-negativeSum > positiveSum) ? -negativeSum : positiveSum;
						
		/* output result */
		printf("$%.2lf\n", exchange);
	}

    return 0;
}

/* 
 * A solution for the Minesweeper problem.
 * UVa ID: 10189
 */
#include <stdio.h>

#define MINE '*'
#define MATRIX_OFFSET 1

int main (int argc, const char * argv[]) {
	/* number of lines of the mine field */
	long n;
	
	/* number of colums of the mine field */
	long m;
	
	/* iterators for retrieving the content of each field line*/
	long i, j;
	
	/* field number identifier */
	long fieldNumber = 0;

	while(scanf("%ld %ld", &n, &m) != EOF) {
			
		/* 0 0, ends the program */
		if (!n && !m) {
			return 0;
		} else {
			if (fieldNumber > 0) {
				/* 
				 * workaround for the extra line on the output, 
				 * which was giving me a Wrong Answer verdict..
				 * so only insert an extra line if there's more
				 * to come :-) 
				 */
				printf("\n");
			}
		}
		
		/* increment field id */
		fieldNumber++;
				
		/* a bidimensional array representing the input mine field */
		char inputField[n + MATRIX_OFFSET + 1][m + MATRIX_OFFSET + 1];
		
		/* a bidimensional array to output the mine field */
		int outputField[n + MATRIX_OFFSET + 1][m + MATRIX_OFFSET + 1];
		
		/* temporary variable to retrieve mine field lines */
		char line[m];
		
		/* init, O(n2) */
		for (i = 0; i < n + MATRIX_OFFSET + 1; i++) {
			for (j = 0; j < m + MATRIX_OFFSET + 1; j++) {
				outputField[i][j] = 0;
			}
		}
		
		/* read mine field, O(n2) */
		for (i = 0; i < n; i++) {
			scanf("%s\n",line);
			for (j = MATRIX_OFFSET; j < m + MATRIX_OFFSET; j++) {
				inputField[i + MATRIX_OFFSET][j] = line[j - MATRIX_OFFSET];
			}
		}
		
		/* update output, O(n2) */ 
		for (i = MATRIX_OFFSET; i < n + MATRIX_OFFSET; i++) {
			for (j = MATRIX_OFFSET; j < m + MATRIX_OFFSET; j++) {
				if (inputField[i][j] == MINE) {
				
					/* upper neighbours */
					outputField[i-1][j-1]++;
					outputField[i-1][j]++;
					outputField[i-1][j+1]++;
					
					/* same level neighbours */
					outputField[i][j-1]++;
					outputField[i][j+1]++;
					
					/* lower neighbours */
					outputField[i+1][j-1]++;
					outputField[i+1][j]++;
					outputField[i+1][j+1]++;
				}
			}
		}
		
		/* present output, O(n2) */
		printf("Field #%ld:\n",fieldNumber);
		for (i = MATRIX_OFFSET; i < n + MATRIX_OFFSET; i++) {
			for (j = MATRIX_OFFSET; j < m + MATRIX_OFFSET; j++) {
				if (inputField[i][j] == MINE)
					printf("%c", MINE);
				else	
					printf("%d",outputField[i][j]);
			}
			printf("\n");
		}

	}

    return 0;
}

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

/* minimum required number of parameters */
#define MIN_REQUIRED 2

/* display usage */
int help() {
   printf("Usage: myprogram [-s <arg0>] [-n <arg1>] [-true]\n");
   printf("\t-s: a string a\n");
   printf("\t-n: a number\n");
   printf("\t-true: a single parameter\n");

   return 1;
}

/* main */
int main(int argc, char *argv[]) {
   if (argc < MIN_REQUIRED) {
      return help();
   }
   int i;

   /* iterate over all arguments */
   for (i = 1; i < (argc - 1); i++) {
       if (strcmp("-s", argv[i]) == 0) {
          /* do something with it */ 
          printf("string = %s\n", argv[++i]);
          continue;
       }
       if (strcmp("-n", argv[i]) == 0) {
          /* do something with it. for example, convert it to an integer */
          printf("number = %i\n", atoi(argv[++i]));
          continue;
       }
       if (strcmp("-true", argv[i]) == 0) {
          printf("true activated\n");
          continue;
       }
       return help();
   }
   return 0;
}

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

#ifdef __OPTIMIZE__
#define __OPT__ 1
#else
#define __OPT__ 0
#endif

#ifdef __OPTIMIZE_SIZE__
#define __OPT_SIZE__ 1
#else
#define __OPT_SIZE__ 0
#endif

#define err_print(args...) __err_print(__FILE__, __FUNCTION__, __LINE__, __DATE__ " " __TIME__, __VERSION__, __OPT__, __OPT_SIZE__, ##args)
void __err_print(char *file, char *function, int line, char *date, char *version, int opt, int opt_size, char *txt, ...)
{
        va_list argp;

        puts("** ERROR! **");
        printf("File:                 \t %s\n",file);
        printf("Function:             \t %s\n",function);
        printf("Line:                 \t %d\n",line);
        printf("Compilation date:     \t %s\n",date);
        printf("Compilator version:   \t %s\n",version);
        printf("Optimization:         \t %s\n",opt==1 ? "Yes" : "No");
        printf("Size optimization:    \t %s\n",opt_size==1 ? "Yes" : "No");

        if (txt == NULL)
                return;
        puts("Description:\n>>>");
        va_start(argp, txt);
        vprintf(txt, argp);
        va_end(argp);
        puts("\n<<<");
}

void other_function() {
        err_print("other %s (%d+%d=%d)", "description",2,2,5);
}

int main() {
        err_print("test %d", 2);
        puts("");
        other_function();
        return 0;
}

void dijkstra2(int s) {
	int queue[GRAPHSIZE];
	char inQueue[GRAPHSIZE];
	int begq = 0,
	    endq = 0;
	int i, mini;
	int visited[GRAPHSIZE];

	for (i = 1; i <= n; ++i) {
		d2[i] = INFINITY;
		visited[i] = 0; /* the i-th element has not yet been visited */
		inQueue[i] = 0;
	}

	d2[s] = 0;
	queue[endq] = s;
	endq = (endq + 1) % GRAPHSIZE;


	while (begq != endq) {
		mini = queue[begq];
		begq = (begq + 1) % GRAPHSIZE;
		inQueue[mini] = 0;

		visited[mini] = 1;

		for (i = 1; i <= n; ++i)
			if (dist[mini][i])
				if (d2[mini] + dist[mini][i] < d2[i]) { 
					d2[i] = d2[mini] + dist[mini][i];
					if (!inQueue[i]) {
						queue[endq] = i;
						endq = (endq + 1) % GRAPHSIZE;
						inQueue[i] = 1;
					}
				}
	}
}

#include <stdio.h>

int n;
float a[10][11];

void forwardSubstitution() {
	int i, j, k, max;
	float t;
	for (i = 0; i < n; ++i) {
		max = i;
		for (j = i + 1; j < n; ++j)
			if (a[j][i] > a[max][i])
				max = j;
		
		for (j = 0; j < n + 1; ++j) {
			t = a[max][j];
			a[max][j] = a[i][j];
			a[i][j] = t;
		}
		
		for (j = n; j >= i; --j)
			for (k = i + 1; k < n; ++k)
				a[k][j] -= a[k][i]/a[i][i] * a[i][j];

/*		for (k = 0; k < n; ++k) {
			for (j = 0; j < n + 1; ++j)
				printf("%.2f\t", a[k][j]);
			printf("