/* 
 * Solution for "Carmichael Numbers" problem.
 * UVa ID: 10006
 */
#include <iostream>
#include <math.h>

#define MAXPRIME 65001

using namespace std;

/*
 * Modular exponentiation algorithm. Returns b^e mod m.
 */
unsigned long long fast_mod_pow(unsigned long long b, unsigned long long e, unsigned long long m) {
    unsigned long long r = 1;
    while (e > 0) {
        if ((e & 1) == 1) {
	    r = (r * b) % m;
        }
        e >>= 1;
        b = (b * b) % m;
    }
    return r;
}

/* 
 * Generates all prime numbers up to MAXPRIME. Based on
 * the Sieve of Eratosthenes.
 */
void gen_primes(bool p[]) {
    p[0] = p[1] = false;
	
    /* 
     * starting at number 2 and going to the upper limit, mark 
     * all numbers as potential primes 
     */  
    for (int i=2; i<MAXPRIME; i++) {
        p[i] = true;
    }
	
    int m = floor(sqrt(MAXPRIME));
    int n;
    /* 
     * mark all multiples of a prime as non-primes. this has to be done for primes 
     * only up to the square root, since every number in the array has at least 
     * one factor smaller than the square root of the limit. 
     */
    for (int i=2; i<m; i++) {
        if (p[i]) {
       	    n = MAXPRIME / i;
	    for (int j=2; j<=n; j++) {
	        p[i * j] = false;
	    }
	}
    }
}

/* generates all carmichael numbers up to the given limit by performing the fermat test */
void gen_carmi(bool c[], bool p[]) {

    /* initialize carmichael numbers array with false */
    memset(c, 0, MAXPRIME * sizeof(bool));
	
    /* 
     * starting from the first non-prime, mark all 
     * odd numbers as potential carmichael numbers 
     */
    for (int i=9; i<MAXPRIME; i+=2) {
	c[i] = true;
    }
	
    /* 
     * again, for all odd numbers, we exclude the primes and perform
     * the fermat test for 2 <= a <= n-1.
     */
    for (int n=9; n<MAXPRIME; n+=2) {
	/* VERY IMPORTANT! check first if this number is prime, otherwise we get TLE */
	if (p[n]) {
	    c[n] = false;
	    continue;
	}
	for (int a=2; a<=n-1; a++) {
	    if (fast_mod_pow(a,n,n) != a) {
	        c[n] = false;
		break;
	    } 
	}	
    }
}

/* main */
int main() {
    unsigned long long n; /* number */
    unsigned long long a; /* a of the fermat test */
    bool prime[MAXPRIME]; /* prime numbers array */
    bool carmi[MAXPRIME]; /* carmichael numbers array */
	
    gen_primes(prime);
    gen_carmi(carmi, prime);
	
    while (cin >> n && (n != 0)) {	
        if (carmi[n]) {
            cout << "The number " << n << " is a Carmichael number." << endl;
        } else {
            cout << n << " is normal." << endl;
        }
    }
    return 0;
}

/*
 * Solution for the "Binomial Showdown" problem.
 * UVa ID: 530
 */

#include <iostream>

using namespace std;

/* main */
int main() {
    int n, k;
    unsigned long long r; /* result */

    while(cin >> n >> k && ((n != 0) || (k != 0))) {
        /* init result */
        r = 1;

        /* if k is more than half of n, then use the complement */
        if(k > (n / 2)) {
            k = n - k;
        }

        /*         
         * C(n,k) = n! / (k!(n-k)!) =
         * (n)(n-1)(...)(n-k+1) / 2*3*4*(...)*k
         */ 
        for (int i=0; i<k; i++) {
            r = r * (n - i);   /* (n)(n-1)(...)(n-k+1) */
            r = r / (1 + i);   /* 2*3*4*(...)*k */
        }
        cout << r << endl;
    }
}

/*
 * Solution for the "Reverse and Add" problem.
 * UVa ID: 10018
 */
#include <iostream>

#define NDIGITS 100

using namespace std;

/* returns the reversed number */
unsigned long long reverse(unsigned long long number) {
	unsigned long long m = 0; /* reversed number */
	int digits[NDIGITS]; /* digits array */
	int pos = 0, power = 1;
	
	/* init */
	for (int i=0; i<NDIGITS; i++) {
		digits[i] = 0;
	}
	
	/* retrieve all digits */
	while (number > 0) {
		digits[pos++] = number % 10;
		number = number / 10;
	}

	/* multiply the reversed digits by the powers of ten */
	for (int i=pos-1; i>=0; i--) {
		m += power * digits[i];
		power *= 10;
	}
	
	return m;
}

/* main */
int main() {
	int nc; /* number of cases */
	int m; /* minimum number of iterations */
	unsigned long long n; /* number */
	
	cin >> nc;
	
	/* reverse and add.. */
	for (int i=0; i<nc; i++) {
		cin >> n;
		m = 0;
		while (true) {
			if (reverse(n) == n) {
				break;
			} else {
				n += reverse(n);
				m++;
			}
		}
		cout << m << " " << n << endl;
	}
	
	return 0;
} 

/**
 * Solution for the "Primary Arithmetic" problem.
 * UVa ID: 10035
 */ 
#include <iostream.h> 
#include <stdlib.h> 

using namespace std; 

int main() {
    unsigned long long n1; /* 1st number */ 
    unsigned long long n2; /* 2nd number */ 
    int carry = 0; /* carry */ 
    int sum = 0; /* temporary sum */ 
    int count = 0; /* carry counter */ 

    while(cin >> n1 >> n2 && ((n1 > 0) || (n2 > 0))) { 
        carry = 0; 
	count = 0; 
	sum = 0; 

	/* while there's still something.. */ 
	while ((n1 > 0) || (n2 > 0)) { 
	    /* sum the two right-most digits */ 
	    sum = carry + (n1 % 10) + (n2 % 10); 

	    if (sum >= 10) { 
		count++; 
	    } 
			
	    /* get the carry by dividing the sum of the two digits */ 
	    carry = sum / 10; 

	    /* 'reduce' the numbers by ten, to update the right-most digits */ 
	    n1 /= 10; 
            n2 /= 10; 
	} 
		
	if (count == 0) { 
            cout << "No carry operation." << endl; 
	} else if (count == 1) { 
	    cout << "1 carry operation." << endl; 
	} else { 
            cout << count << " carry operations." << endl; 
        } 
    } 

    return 0;
} 

/* 
 * Solution for "Shoemaker" problem.
 * UVa ID: 10026
 */
#include <iostream>

#define NJOBS 1000

using namespace std;

int jobs[NJOBS]; /* jobs */
double p[NJOBS]; /* priority */

/* main */
int main() {
    int nc;	/* number of cases */
	int nj; /* number of jobs */
	int ct;	/* completion time */
	int dp; /* daily penalty */
	
    cin >> nc;
	
	/* for each test case.. */
    for (int i=0; i<nc; i++) {
		cin >> nj;
		
		/* init input */
		for (int i=0; i<nj; i++) {
			cin >> ct >> dp;
			jobs[i] = i;
			/* priority is daily penalty divided by completion time (minimal fine) */
			p[i] = double(dp) / ct;
		}
		
		int j, k, tmp;
		
		/* sort jobs by priority */
		for (int i=0; i<nj-1; i++) {
			for (j=i+1, k=i; j<nj; j++) {
				if( (p[jobs[j]] > p[jobs[k]]) || ((p[jobs[j]] == p[jobs[k]]) && (jobs[j] < jobs[k])) ) {
					k=j;
				}
			}
			tmp = jobs[i]; 
			jobs[i] = jobs[k]; 
			jobs[k] = tmp;
		}
		
		/* output */
		for (int i=0; i<nj; i++) {
			if(i > 0) { 
				cout << " ";
			}
			cout << jobs[i] + 1;
		}
		cout << endl;
		if (i < nc-1) {
			cout << endl;
		}
    }
	
    return 0;
}

/* 
 * Solution for "Stack 'em Up" problem.
 * UVa ID: 10205
 */
#include <iostream>

#define NVALUES 13
#define NSUITS 4
#define NCARDS 52
#define NSHUFFLES 100
#define WSIZE 9

using namespace std;

char values[NVALUES][WSIZE] = {"2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King", "Ace"};
char suits[NSUITS][WSIZE] = {"Clubs", "Diamonds", "Hearts", "Spades"};
int shuffles[NSHUFFLES][NCARDS];
int deck[NCARDS];

/* read all dealer shuffles */
void read_shuffles(int n_shuff) {
	for(int i=0; i<n_shuff; i++) {
		for (int j=0; j<NCARDS; j++) {
			cin >> shuffles[i][j];
		}
	}
}

/* shuffle the deck with one of the known shuffles */
void shuffle_deck(int s_id) {
	int tmpdeck[NCARDS];
	for (int i=0; i<NCARDS; i++) {
		tmpdeck[i] = deck[shuffles[s_id][i] - 1];
	}
	for (int i=0; i<NCARDS;i++) {
		deck[i] = tmpdeck[i];
	}
}

/* main */
int main (int argc, const char *argv[]) {
	int nc; /* number of cases */
	int ns;	/* number of shuffles */
	int s; /* current shuffle */
		
	cin >> nc;
		
	for (int i=0; i<nc; i++) {	
		cin >> ns;
			
		/* initialize deck */
		for (int p=0; p<NCARDS; p++) {
			deck[p] = p;
		}
		
		/* read list of known shuffles */
		read_shuffles(ns);
		
		/* shuffle deck */
		for (int j=0; j<ns; j++) {
			cin >> s;
			shuffle_deck(s - 1);
		}

		/* print deck */
		for (int k=0; k<NCARDS; k++) {
			cout << values[deck[k] % NVALUES] << " of " << suits[deck[k] / NVALUES] << endl;
		}
		if (i < (nc - 1)) {
			cout << endl;
		}
	}
	
}

/* 
 * Solution for the "Hartals" problem.
 * UVa ID: 10050
 */
#include <iostream>
 
#define NDAYS 3651
 
using namespace std;

/* simulation time (in days) */
int st[NDAYS]; 
 
/* main */
int main (int argc, const char *argv[]) {
	int nc; /* number of cases */
	int nd; /* number of days */
	int np; /* number of political parties */
	int h; /* current hartal number */
	int dl;	/* days lost */
	
	cin >> nc;
	
	/* for each case.. */
	for (int i=0; i<nc; i++) {
		cin >> nd;
		cin >> np;		
		
		/* initialize simulation table */
		for (int j=0; j<=nd; j++) {
			st[j] = 0;
		}
		dl = 0; /* init days lost counter */
		
		/* update with hartal for each party */
		for (int j=0; j<np; j++) {
			cin >> h;
			for (int k=1; k*h-1<=nd; k++) {
				st[k*h-1] = 1; /* set lost day flag */
			}
		}
		
		/* calculate number of days lost */
		for (int j=0; j<nd; j++) {
			/* if it's not a friday or a saturday */
			if ((j%7 != 5) && (j%7 != 6) && (st[j] == 1)) {
				dl++;
			}
		}
		cout << dl << endl;
	}
	
}

ArrayList<Object> list = new ArrayList<Object>();

/* 
 * 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;
}