#!/bin/sh
# This is a shell archive (produced by shar 3.49)
# To extract the files from this archive, save it to a file, remove
# everything above the "!/bin/sh" line above, and type "sh file_name".
#
# made 06/14/1993 20:45 UTC by paul@uxc.cso.uiuc.edu
# Source directory /tmp/p
#
# existing files will NOT be overwritten unless -c is specified
#
# This shar contains:
# length  mode       name
# ------ ---------- ------------------------------------------
#    296 -rw-r--r-- Makefile
#   3165 -r--r--r-- factor.6
#   8160 -r--r--r-- factor.c
#  32129 -r--r--r-- pattern.c
#  39958 -r--r--r-- pr_tbl.c
#  10372 -r--r--r-- primes.c
#   1790 -r--r--r-- primes.h
#
# ============= Makefile ==============
if test -f 'Makefile' -a X"$1" != X"-c"; then
	echo 'x - skipping Makefile (File already exists)'
else
echo 'x - extracting Makefile (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'Makefile' &&
#	@(#)Makefile	5.1 (Berkeley) 5/11/90
X
HDRS= primes.h
SRCS= pattern.c pr_tbl.c primes.c factor.c
OBJS= pattern.o pr_tbl.o primes.o
X
CC=cc
CFLAGS=-O
X
all: primes factor
X
primes:	${OBJS}
X	${CC} ${CFLAGS} -o primes ${OBJS} -lm
X
factor: factor.o pr_tbl.o
X	${CC} ${CFLAGS} -o factor factor.o pr_tbl.o
SHAR_EOF
chmod 0644 Makefile ||
echo 'restore of Makefile failed'
Wc_c="`wc -c < 'Makefile'`"
test 296 -eq "$Wc_c" ||
	echo 'Makefile: original size 296, current size' "$Wc_c"
fi
# ============= factor.6 ==============
if test -f 'factor.6' -a X"$1" != X"-c"; then
	echo 'x - skipping factor.6 (File already exists)'
else
echo 'x - extracting factor.6 (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'factor.6' &&
.\" Copyright (c) 1989 The Regents of the University of California.
.\" All rights reserved.
.\"
.\" This code is derived from software contributed to Berkeley by
.\" Landon Curt Noll.
.\"
.\" Redistribution and use in source and binary forms are permitted provided
.\" that: (1) source distributions retain this entire copyright notice and
.\" comment, and (2) distributions including binaries display the following
.\" acknowledgement:  ``This product includes software developed by the
.\" University of California, Berkeley and its contributors'' in the
.\" documentation or other materials provided with the distribution and in
.\" all advertising materials mentioning features or use of this software.
.\" Neither the name of the University nor the names of its contributors may
.\" be used to endorse or promote products derived from this software without
.\" specific prior written permission.
.\" THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
.\" WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
.\" MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
.\"
.\"	@(#)factor.6	5.3 (Berkeley) 6/23/90
.\"
.\"
.\" By: Landon Curt Noll   chongo@toad.com,   ...!{sun,tolsoft}!hoptoad!chongo
.\"
.\"   chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
.\"
.TH FACTOR 6 "June 23, 1990"
.UC 7
.SH NAME
factor, primes \- factor a number, generate primes
.SH SYNOPSIS
.B factor
[ number ] ...
.PP
.B primes
[ start [ stop ]]
.SH DESCRIPTION
The
.I factor
utility will factor integers between -2147483648 and 2147483647 inclusive.
When a number is factored, it is printed, followed by a ``:'',
and the list of factors on a single line.
Factors are listed in ascending order, and are preceded by a space.
If a factor divides a value more than once, it will be printed
more than once.
.PP
When
.I factor
is invoked with one or more arguments,
each argument will be factored.
.PP
When
.I factor
is invoked with no arguments,
.I factor
reads numbers, one per line, from standard input, until end of file or error.
Leading white-space and empty lines are ignored.
Numbers may be preceded by a single - or +.
Numbers are terminated by a non-digit character (such as a newline).
After a number is read, it is factored.
Input lines must not be longer than 255 characters.
.PP
The
.I primes
utility prints primes in ascending order, one per line, starting at or above
.B start
and continuing until, but not including
.B stop.
The
.B start 
value must be at least 0 and not greater than
.B stop.\&
The
.B stop
value must not be greater than 4294967295.
The default value of
.B stop
is 4294967295.
.PP
When the
.I primes
utility is invoked with no arguments,
.B start
is read from standard input.
.B Stop
is taken to be 4294967295.
The
.B start
value may be preceded by a single +.
The
.B start
value is terminated by a non-digit character (such as a newline).
The input line must not be longer than 255 characters.
.SH DIAGNOSTICS
Out of range or invalid input results in `ouch' being 
written to standard error.
.SH BUGS
.I Factor
cannot handle the ``10 most wanted'' factor list,
.I primes
won't get you a world record.
SHAR_EOF
chmod 0444 factor.6 ||
echo 'restore of factor.6 failed'
Wc_c="`wc -c < 'factor.6'`"
test 3165 -eq "$Wc_c" ||
	echo 'factor.6: original size 3165, current size' "$Wc_c"
fi
# ============= factor.c ==============
if test -f 'factor.c' -a X"$1" != X"-c"; then
	echo 'x - skipping factor.c (File already exists)'
else
echo 'x - extracting factor.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'factor.c' &&
/*
X * Copyright (c) 1989 The Regents of the University of California.
X * All rights reserved.
X *
X * This code is derived from software contributed to Berkeley by
X * Landon Curt Noll.
X *
X * Redistribution and use in source and binary forms are permitted
X * provided that: (1) source distributions retain this entire copyright
X * notice and comment, and (2) distributions including binaries display
X * the following acknowledgement:  ``This product includes software
X * developed by the University of California, Berkeley and its contributors''
X * in the documentation or other materials provided with the distribution
X * and in all advertising materials mentioning features or use of this
X * software. Neither the name of the University nor the names of its
X * contributors may be used to endorse or promote products derived
X * from this software without specific prior written permission.
X * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
X * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
X * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
X */
X
#ifndef lint
char copyright[] =
"@(#) Copyright (c) 1989 The Regents of the University of California.\n\
X All rights reserved.\n";
#endif /* not lint */
X
#ifndef lint
static char sccsid[] = "@(#)factor.c	4.4 (Berkeley) 6/1/90";
#endif /* not lint */
X
/*
X * factor - factor a number into primes
X *
X * By: Landon Curt Noll   chongo@toad.com,   ...!{sun,tolsoft}!hoptoad!chongo
X *
X *   chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
X *
X * usage:
X *	factor [number] ...
X *
X * The form of the output is:
X *
X *	number: factor1 factor1 factor2 factor3 factor3 factor3 ...
X *
X * where factor1 < factor2 < factor3 < ...
X *
X * If no args are given, the list of numbers are read from stdin.
X */
X
#include <stdio.h>
#include <ctype.h>
#include "primes.h"
X
/*
X * prime[i] is the (i-1)th prime.
X *
X * We are able to sieve 2^32-1 because this byte table yields all primes 
X * up to 65537 and 65537^2 > 2^32-1.
X */
extern ubig prime[];
extern ubig *pr_limit;	/* largest prime in the prime array */
X
#define MAX_LINE 255	/* max line allowed on stdin */
X
void pr_fact();		/* print factors of a value */
long small_fact();	/* find smallest factor of a value */
char *read_num_buf();	/* read a number buffer */
char *program;		/* name of this program */
X
main(argc, argv)
X	int argc;	/* arg count */
X	char *argv[];	/* the args */
{
X	int arg;	/* which arg to factor */
X	long val;	/* the value to factor */
X	char buf[MAX_LINE+1];	/* input buffer */
X
X	/* parse args */
X	program = argv[0];
X	if (argc >= 2) {
X
X		/* factor each arg */
X		for (arg=1; arg < argc; ++arg) {
X
X			/* process the buffer */
X			if (read_num_buf(NULL, argv[arg]) == NULL) {
X				fprintf(stderr, "%s: ouch\n", program);
X				exit(1);
X			}
X
X			/* factor the argument */
X			if (sscanf(argv[arg], "%ld", &val) == 1) {
X				pr_fact(val);
X			} else {
X				fprintf(stderr, "%s: ouch\n", program);
X				exit(1);
X			}
X		}
X
X	/* no args supplied, read numbers from stdin */
X	} else {
X		/*
X		 * read asciii numbers from input
X		 */
X		while (read_num_buf(stdin, buf) != NULL) {
X
X			/* factor the argument */
X			if (sscanf(buf, "%ld", &val) == 1) {
X				pr_fact(val);
X			}
X		}
X	}
X	exit(0);
}
X
/*
X * read_num_buf - read a number buffer from a stream
X *
X * Read a number on a line of the form:
X *
X *	^[ \t]*\([+-]?[0-9][0-9]\)*.*$
X *
X * where ? is a 1-or-0 operator and the number is within \( \).
X *
X * If does not match the above pattern, it is ignored and a new
X * line is read.  If the number is too large or small, we will
X * print ouch and read a new line.
X *
X * We have to be very careful on how we check the magnitude of the
X * input.  We can not use numeric checks because of the need to
X * check values against maximum numeric values.
X *
X * This routine will return a line containing a ascii number between
X * NEG_SEMIBIG and SEMIBIG, or it will return NULL.
X *
X * If the stream is NULL then buf will be processed as if were
X * a single line stream.
X *
X * returns:
X *	char *	pointer to leading digit, + or -
X *	NULL	EOF or error
X */
char *
read_num_buf(input, buf)
X	FILE *input;		/* input stream or NULL */
X	char *buf;		/* input buffer */
{
X	static char limit[MAX_LINE+1];	/* ascii value of SEMIBIG */
X	static int limit_len;		/* digit count of limit */
X	static char neg_limit[MAX_LINE+1];	/* value of NEG_SEMIBIG */
X	static int neg_limit_len;		/* digit count of neg_limit */
X	int len;			/* digits in input (excluding +/-) */
X	char *s;	/* line start marker */
X	char *d;	/* first digit, skip +/- */
X	char *p;	/* scan pointer */
X	char *z;	/* zero scan pointer */
X
X	/* form the ascii value of SEMIBIG if needed */
X	if (!isascii(limit[0]) || !isdigit(limit[0])) {
X		sprintf(limit, "%ld", SEMIBIG);
X		limit_len = strlen(limit);
X		sprintf(neg_limit, "%ld", NEG_SEMIBIG);
X		neg_limit_len = strlen(neg_limit)-1;	/* exclude - */
X	}
X	
X	/*
X	 * the search for a good line
X	 */
X	if (input != NULL && fgets(buf, MAX_LINE, input) == NULL) {
X		/* error or EOF */
X		return NULL;
X	}
X	do {
X
X		/* ignore leading whitespace */
X		for (s=buf; *s && s < buf+MAX_LINE; ++s) {
X			if (!isascii(*s) || !isspace(*s)) {
X				break;
X			}
X		}
X
X		/* skip over any leading + or - */
X		if (*s == '+' || *s == '-') {
X			d = s+1;
X		} else {
X			d = s;
X		}
X
X		/* note leading zeros */
X		for (z=d; *z && z < buf+MAX_LINE; ++z) {
X			if (*z != '0') {
X				break;
X			}
X		}
X
X		/* scan for the first non-digit */
X		for (p=d; *p && p < buf+MAX_LINE; ++p) {
X			if (!isascii(*p) || !isdigit(*p)) {
X				break;
X			}
X		}
X
X		/* ignore empty lines */
X		if (p == d) {
X			continue;
X		}
X		*p = '\0';
X
X		/* object if too many digits */
X		len = strlen(z);
X		len = (len<=0) ? 1 : len;
X		if (*s == '-') {
X			/* accept if digit count is below limit */
X			if (len < neg_limit_len) {
X				/* we have good input */
X				return s;
X
X			/* reject very large numbers */
X			} else if (len > neg_limit_len) {
X				fprintf(stderr, "%s: ouch\n", program);
X				exit(1);
X
X			/* carefully check against near limit numbers */
X			} else if (strcmp(z, neg_limit+1) > 0) {
X				fprintf(stderr, "%s: ouch\n", program);
X				exit(1);
X			}
X			/* number is near limit, but is under it */
X			return s;
X		
X		} else {
X			/* accept if digit count is below limit */
X			if (len < limit_len) {
X				/* we have good input */
X				return s;
X
X			/* reject very large numbers */
X			} else if (len > limit_len) {
X				fprintf(stderr, "%s: ouch\n", program);
X				exit(1);
X
X			/* carefully check against near limit numbers */
X			} else if (strcmp(z, limit) > 0) {
X				fprintf(stderr, "%s: ouch\n", program);
X				exit(1);
X			}
X			/* number is near limit, but is under it */
X			return s;
X		}
X	} while (input != NULL && fgets(buf, MAX_LINE, input) != NULL);
X
X	/* error or EOF */
X	return NULL;
}
X
X
/*
X * pr_fact - print the factors of a number
X *
X * If the number is 0 or 1, then print the number and return.
X * If the number is < 0, print -1, negate the number and continue
X * processing.
X *
X * Print the factors of the number, from the lowest to the highest.
X * A factor will be printed numtiple times if it divides the value
X * multiple times.
X *
X * Factors are printed with leading tabs.
X */
void
pr_fact(val)
X	long val;	/* factor this value */
{
X	ubig *fact;	/* the factor found */
X
X	/* firewall - catch 0 and 1 */
X	switch (val) {
X	case -2147483648:
X		/* avoid negation problems */
X		puts("-2147483648: -1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2\n");
X		return;
X	case -1:
X		puts("-1: -1\n");
X		return;
X	case 0:
X		exit(0);
X	case 1:
X		puts("1: 1\n");
X		return;
X	default:
X		if (val < 0) {
X			val = -val;
X			printf("%ld: -1", val);
X		} else {
X			printf("%ld:", val);
X		}
X		fflush(stdout);
X		break;
X	}
X
X	/*
X	 * factor value
X	 */
X	fact = &prime[0];
X	while (val > 1) {
X
X		/* look for the smallest factor */
X		do {
X			if (val%(long)*fact == 0) {
X				break;
X			}
X		} while (++fact <= pr_limit);
X
X		/* watch for primes larger than the table */
X		if (fact > pr_limit) {
X			printf(" %ld\n", val);
X			return;
X		}
X
X		/* divide factor out until none are left */
X		do {
X			printf(" %ld", *fact);
X			val /= (long)*fact;
X		} while ((val % (long)*fact) == 0);
X		fflush(stdout);
X		++fact;
X	}
X	putchar('\n');
X	return;
}
SHAR_EOF
chmod 0444 factor.c ||
echo 'restore of factor.c failed'
Wc_c="`wc -c < 'factor.c'`"
test 8160 -eq "$Wc_c" ||
	echo 'factor.c: original size 8160, current size' "$Wc_c"
fi
# ============= pattern.c ==============
if test -f 'pattern.c' -a X"$1" != X"-c"; then
	echo 'x - skipping pattern.c (File already exists)'
else
echo 'x - extracting pattern.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'pattern.c' &&
/*
X * Copyright (c) 1989 The Regents of the University of California.
X * All rights reserved.
X *
X * This code is derived from software contributed to Berkeley by
X * Landon Curt Noll.
X *
X * Redistribution and use in source and binary forms are permitted
X * provided that: (1) source distributions retain this entire copyright
X * notice and comment, and (2) distributions including binaries display
X * the following acknowledgement:  ``This product includes software
X * developed by the University of California, Berkeley and its contributors''
X * in the documentation or other materials provided with the distribution
X * and in all advertising materials mentioning features or use of this
X * software. Neither the name of the University nor the names of its
X * contributors may be used to endorse or promote products derived
X * from this software without specific prior written permission.
X * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
X * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
X * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
X */
X
#ifndef lint
static char sccsid[] = "@(#)pattern.c	5.2 (Berkeley) 6/1/90";
#endif /* not lint */
X
/*
X * pattern - the Eratosthenes sieve on odd numbers for 3,5,7,11 and 13
X *
X * By: Landon Curt Noll                             chongo@toad.com
X *
X *   chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
X *
X * To avoid excessive sieves for small factors, we use the table below to 
X * setup our sieve blocks.  Each element represents a odd number starting 
X * with 1.  All non-zero elements are factors of 3, 5, 7, 11 and 13.
X */
X
char pattern[] = {
1,0,0,0,0,0,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,
1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,0,0,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,
1,0,0,1,0,1,0,0,1,0,0,1,1,0,0,0,0,1,1,0,1,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,1,0,1,
0,0,1,1,0,0,0,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,0,0,0,0,1,0,1,
1,0,1,0,0,1,0,0,0,1,0,0,1,0,0,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,
1,0,0,1,0,1,0,0,0,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,
0,0,0,0,0,1,0,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0,1,0,0,
1,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,0,
0,0,1,1,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,
1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,1,0,0,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,
0,0,0,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,
1,0,1,0,0,0,0,0,0,1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,0,0,0,1,0,0,0,0,1,0,0,0,
1,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,
0,0,1,1,0,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,0,1,0,0,1,0,1,
1,0,1,0,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,0,1,0,0,0,1,0,1,1,0,0,1,0,1,0,0,0,
1,0,0,0,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,0,0,1,
1,0,0,0,0,1,0,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,0,0,0,1,1,0,0,
1,0,0,1,0,0,0,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,0,0,0,0,1,0,1,
0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,0,1,0,0,0,0,1,
1,0,1,1,0,1,0,0,1,1,0,0,0,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,
0,0,0,1,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,
0,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0,
1,0,1,1,0,0,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,0,
0,0,0,1,0,0,0,0,1,0,0,1,1,0,1,0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,
1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,0,0,1,0,0,1,
1,0,0,1,0,1,0,0,0,0,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,
1,0,1,0,0,1,0,0,0,1,0,0,1,0,0,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,0,1,0,0,0,
0,0,1,1,0,1,0,0,0,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,0,0,0,1,0,0,1,0,1,
0,0,0,0,0,0,0,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,
1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,0,1,0,1,0,0,1,
1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,
1,0,1,0,0,0,0,0,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,1,0,0,1,0,1,1,0,0,0,0,1,1,0,0,
0,0,1,1,0,1,0,0,0,0,0,0,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,0,0,1,0,0,0,0,1,0,0,1,
0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,0,
0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,0,0,0,1,
1,0,0,0,0,1,0,0,1,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,0,0,0,0,0,1,1,0,0,1,0,1,1,0,0,
1,0,1,0,0,1,0,0,0,0,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,
1,0,0,0,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,0,1,0,1,0,0,1,
0,0,1,1,0,0,0,0,0,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,0,0,0,0,1,0,1,
1,0,0,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,0,1,0,0,0,0,1,
1,0,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,1,0,1,
0,0,1,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,0,1,0,0,
1,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,0,
0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,0,0,0,0,1,0,1,
1,0,0,1,0,0,0,0,1,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,0,0,1,0,0,0,1,0,1,0,0,0,
1,0,0,1,0,0,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,
1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,0,0,
1,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,
0,0,1,0,0,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,0,1,0,0,0,0,1,
1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,
1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,
1,0,0,0,0,1,0,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,0,0,0,0,0,1,1,0,0,
1,0,1,1,0,0,0,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,0,1,0,0,1,0,0,0,0,1,1,0,1,
0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,1,0,1,1,0,0,0,0,0,1,0,0,0,0,1,
0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,0,0,1,0,0,1,
0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,0,
1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,1,0,0,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0,
1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,0,0,0,0,1,0,0,1,0,1,1,0,1,
0,0,0,1,0,0,0,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,
1,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,0,0,1,0,0,1,
1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,0,0,0,1,0,1,0,0,1,
1,0,0,0,0,1,0,0,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,0,0,1,1,0,1,1,0,0,0,0,0,1,0,0,
0,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,
0,0,1,0,0,0,0,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,
1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,1,
0,0,0,1,0,1,0,0,1,0,0,0,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,0,0,1,1,0,1,
1,0,1,0,0,0,0,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,
1,0,1,1,0,1,0,0,0,0,0,1,1,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,0,0,1,
0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,1,0,0,0,1,0,0,1,0,1,
0,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,0,1,1,0,0,1,0,0,0,0,1,
1,0,0,0,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,0,0,0,
1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,0,0,0,0,0,1,1,0,0,
1,0,0,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,0,1,0,0,1,0,1,
0,0,1,1,0,0,0,0,1,1,0,1,0,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,0,0,0,0,0,1,0,1,
1,0,1,1,0,1,0,0,0,1,0,0,0,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,
1,0,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,
0,0,1,0,0,1,0,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,0,1,0,0,
1,0,1,0,0,0,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,0,
0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,0,0,0,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,
1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,
1,0,0,1,0,0,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,
1,0,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,0,0,0,1,0,0,0,
1,0,1,1,0,1,0,0,0,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,
0,0,0,1,0,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,1,
1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,0,0,1,0,0,1,0,0,0,1,0,0,1,0,0,1,0,1,0,0,0,
1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,
1,0,0,0,0,1,0,0,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0,1,0,1,1,0,1,0,0,0,0,0,1,1,0,0,
0,0,1,1,0,0,0,0,1,0,0,0,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,0,0,0,1,1,0,1,
0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,0,0,0,0,1,0,0,0,0,0,
1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,
0,0,0,1,0,1,0,0,1,1,0,1,0,0,0,0,0,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,1,0,0,1,0,1,
1,0,1,0,0,1,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0,1,0,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0,
1,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,0,0,1,
0,0,0,1,0,0,0,0,0,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,
1,0,0,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,0,0,0,1,
1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,0,0,0,0,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,
1,0,1,0,0,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,
0,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,
0,0,1,0,0,0,0,0,1,1,0,0,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,0,0,0,0,1,0,0,
1,0,1,1,0,0,0,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,0,
1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,
1,0,1,0,0,0,0,0,0,1,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,0,0,0,1,1,0,0,
1,0,1,1,0,1,0,0,0,0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,0,0,1,
0,0,1,0,0,0,0,0,1,1,0,0,1,0,0,0,0,1,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,0,0,1,
0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,0,0,0,1,0,0,0,0,1,
1,0,0,0,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,0,
1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,0,1,0,0,0,0,1,1,0,0,
1,0,0,1,0,1,0,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,
0,0,1,1,0,0,0,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,0,1,0,1,0,0,0,0,0,0,1,0,1,
0,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,0,0,0,1,0,0,1,
1,0,0,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,
0,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,0,1,0,0,
1,0,1,0,0,1,0,0,1,0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,0,0,0,1,0,0,1,0,0,1,0,1,1,0,0,
0,0,1,1,0,0,0,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,
1,0,0,0,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,
1,0,0,1,0,0,0,0,0,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,0,1,0,0,0,0,0,1,1,0,1,
1,0,0,0,0,1,0,0,0,1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,0,0,1,1,0,0,1,0,0,0,0,0,0,0,0,
1,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,
0,0,1,1,0,0,0,0,1,1,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,
1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,1,0,0,0,
0,0,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,0,0,1,1,0,1,
1,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,0,0,1,0,0,0,0,0,1,1,0,0,
1,0,1,1,0,0,0,0,1,0,0,1,0,0,0,1,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,0,0,0,1,1,0,1,
0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,0,0,0,0,1,0,0,0,0,1,
1,0,1,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,0,0,0,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,
0,0,0,0,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,0,0,1,
1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,0,0,0,0,0,1,1,0,0,
1,0,0,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,0,1,0,0,1,0,1,
0,0,0,1,0,0,0,0,1,0,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,0,0,0,0,1,0,0,1,0,1,
1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,1,0,0,0,0,1,0,0,1,
1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,
0,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,
0,0,1,1,0,0,0,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,1,0,0,0,1,0,0,1,0,0,1,0,0,
0,0,1,0,0,0,0,0,1,1,0,1,1,0,1,0,0,0,1,0,0,0,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,
1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,1,
1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,
1,0,1,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,0,0,0,1,0,0,0,
1,0,1,1,0,1,0,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,0,0,0,0,0,1,0,1,0,0,1,
0,0,0,1,0,0,0,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,1,
0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,0,0,0,1,
1,0,0,0,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,
1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,0,1,0,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,
0,0,0,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,0,0,0,1,1,0,1,
0,0,1,1,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,0,0,1,0,0,0,0,0,0,1,0,0,
1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,
1,0,0,1,0,1,0,0,1,1,0,0,0,0,1,0,0,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0,1,0,1,1,0,1,
0,0,1,0,0,1,0,0,0,0,0,1,1,0,0,1,0,1,0,0,0,0,0,0,1,0,1,1,0,1,1,0,0,0,0,0,1,0,0,
1,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,0,0,0,
0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,
1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,1,
1,0,0,1,0,0,0,0,1,1,0,1,0,0,1,1,0,0,0,0,1,1,0,1,1,0,0,0,0,0,1,0,0,0,0,1,1,0,1,
1,0,1,0,0,1,0,0,0,1,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,0,0,0,1,0,0,0,
1,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,0,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,
0,0,1,1,0,0,0,0,1,1,0,0,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,0,0,0,0,1,0,1,
1,0,1,0,0,0,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,0,0,1,1,0,0,1,0,1,0,0,0,
1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,
1,0,0,0,0,1,0,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,0,0,0,0,0,1,1,0,0,
1,0,1,1,0,0,0,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,1,0,0,0,1,0,0,1,0,0,0,0,1,1,0,1,
0,0,1,0,0,0,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,0,0,1,0,0,0,0,1,
1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,
0,0,0,1,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,
1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,1,0,0,0,0,1,1,0,0,
1,0,1,1,0,1,0,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,0,1,0,0,0,1,0,0,1,0,1,1,0,1,
0,0,0,1,0,0,0,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,
0,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,0,0,1,0,0,1,
1,0,0,1,0,0,0,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,0,
1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,
0,0,1,1,0,1,0,0,1,0,0,1,1,0,0,0,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,0,1,0,0,1,0,1,
0,0,1,0,0,0,0,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,
1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,1,
1,0,0,1,0,1,0,0,0,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,
1,0,0,0,0,0,0,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,0,0,0,1,0,1,1,0,0,0,0,0,1,0,0,
1,0,1,1,0,1,0,0,0,0,0,1,1,0,0,0,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,0,0,1,
0,0,1,1,0,0,0,0,1,1,0,0,0,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,
0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,0,0,0,1,
0,0,0,0,0,1,0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,0,0,1,1,0,0,
1,0,1,0,0,0,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,
1,0,0,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,
0,0,1,1,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,0,0,0,0,1,0,1,
1,0,1,1,0,1,0,0,0,0,0,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,
1,0,0,0,0,1,0,0,1,1,0,0,0,0,0,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,0,0,1,
0,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,0,0,0,0,0,0,1,0,0,
1,0,0,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,0,
0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,0,0,0,0,0,0,1,0,0,1,0,1,
1,0,0,1,0,1,0,0,1,0,0,0,0,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,
1,0,0,1,0,0,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,
0,0,1,0,0,1,0,0,0,1,0,0,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,0,0,0,1,0,0,0,
1,0,1,1,0,0,0,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,0,
0,0,1,1,0,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,
1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,1,0,0,0,
1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,
1,0,0,0,0,1,0,0,0,0,0,1,1,0,0,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,0,0,0,1,0,0,0,
1,0,1,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1,1,0,1,
0,0,0,1,0,0,0,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,0,0,1,1,0,0,0,0,0,1,0,0,0,0,1,
1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,
0,0,0,1,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,
1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0,
0,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,0,0,0,1,1,0,1,
0,0,0,1,0,0,0,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,0,0,1,0,0,0,1,0,0,1,0,0,
1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,0,0,1,0,0,1,
1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,0,1,0,0,1,0,1,0,0,1,
1,0,1,0,0,1,0,0,0,0,0,0,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,
0,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,0,0,0,1,
0,0,1,0,0,0,0,0,0,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,
1,0,0,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,0,1,0,0,0,0,0,1,1,0,0,1,0,0,0,0,1,
1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,0,0,0,0,1,0,1,1,0,1,
1,0,1,0,0,0,0,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,0,0,0,1,1,0,0,
1,0,1,1,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,0,0,1,
0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,0,0,0,1,0,1,
0,0,1,1,0,0,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,1,0,0,0,0,0,
1,0,0,0,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,
1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,
1,0,0,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,0,0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,
0,0,1,0,0,0,0,0,1,1,0,1,0,0,0,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,0,0,0,0,0,0,1,
1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,0,0,0,1,0,1,0,0,1,
1,0,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,
0,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,0,0,1,0,0,
1,0,1,0,0,1,0,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,0,0,1,0,1,1,0,0,
0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,
0,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,0,0,0,1,0,0,1,
1,0,0,1,0,0,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,
1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,0,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,0,1,0,0,0,
1,0,1,1,0,1,0,0,1,0,0,0,1,0,0,0,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,1,0,1,1,0,1,
0,0,1,1,0,0,0,0,1,0,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,
1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,1,0,0,0,
1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,
1,0,0,0,0,1,0,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,0,0,0,0,1,1,0,1,0,0,0,0,0,0,1,0,0,
1,0,1,1,0,0,0,0,1,0,0,1,0,0,0,1,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,0,0,1,1,0,1,
0,0,1,1,0,0,0,0,0,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,0,0,0,0,1,0,0,0,0,1,
1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,
0,0,0,1,0,1,0,0,1,1,0,0,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,0,0,0,1,0,1,
1,0,1,0,0,0,0,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,0,0,1,1,0,0,0,0,1,1,0,0,
1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,0,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,1,
0,0,0,1,0,0,0,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,0,0,0,1,0,0,1,0,1,
1,0,1,1,0,0,0,0,1,0,0,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0,1,0,1,1,0,0,0,0,1,0,0,1,
1,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,
1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,0,0,0,1,1,0,0,
0,0,0,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,
0,0,1,0,0,0,0,0,1,1,0,1,1,0,1,0,0,0,0,0,0,1,0,1,0,0,1,1,0,0,0,0,0,1,0,0,1,0,0,
1,0,1,1,0,1,0,0,1,1,0,0,0,0,1,1,0,1,1,0,0,0,0,0,1,0,0,0,0,1,1,0,0,1,0,1,0,0,1,
1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,
0,0,1,0,0,0,0,0,0,1,0,0,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,0,0,0,1,1,0,0,
1,0,1,1,0,0,0,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,0,0,0,
0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,1,0,0,0,0,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,
0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,0,0,0,1,
1,0,0,0,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,
1,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,0,0,0,1,0,0,0,
1,0,0,1,0,1,0,0,0,0,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,
0,0,0,1,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,1,0,1,
1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,
1,0,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,
0,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,0,1,0,0,
0,0,1,0,0,1,0,0,1,0,0,0,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,0,0,0,1,1,0,0,
0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,0,
1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,
1,0,0,1,0,0,0,0,1,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,
1,0,1,0,0,1,0,0,0,0,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,0,1,0,0,0,0,1,0,0,0,
1,0,1,0,0,1,0,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,0,0,1,
0,0,1,1,0,0,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,
1,0,0,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,0,0,
1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,1,0,1,
1,0,0,0,0,1,0,0,0,0,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,0,0,0,1,1,0,0,
1,0,1,1,0,0,0,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,1,0,0,0,1,0,0,1,0,0,0,0,1,1,0,1,
0,0,1,1,0,0,0,0,0,1,0,0,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,1,
1,0,1,1,0,0,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,0,
0,0,0,1,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,
1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,
1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,1,
0,0,0,0,0,0,0,0,1,0,0,1,1,0,0,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,0,1,0,0,0,0,1,
1,0,1,1,0,0,0,0,0,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,0,0,0,0,0,1,0,0,1,
1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,0,0,0,1,
1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,0,0,0,1,1,0,0,
0,0,1,1,0,1,0,0,1,0,0,1,0,0,0,1,0,1,1,0,1,0,0,0,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,
0,0,1,0,0,0,0,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,
0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,0,0,1,0,0,1,
1,0,0,1,0,0,0,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,0,
1,0,1,0,0,0,0,0,0,1,0,1,0,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,0,0,0,1,1,0,0,
1,0,1,1,0,1,0,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,0,1,0,1,0,0,1,
0,0,1,1,0,0,0,0,1,0,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,
0,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,0,0,0,1,
1,0,0,0,0,1,0,0,0,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,1,0,0,0,1,0,1,1,0,0,
1,0,0,0,0,1,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,0,0,1,0,0,1,1,0,0,0,0,0,1,0,0,
1,0,0,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,
0,0,1,1,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,0,0,0,0,0,0,1,0,1,
1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,
0,0,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,0,0,0,0,1,1,0,1,
0,0,1,0,0,0,0,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,0,0,1,1,0,0,0,0,0,1,0,0,
1,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,0,
0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,0,0,1,0,0,0,1,0,0,1,0,1,
1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,
1,0,0,0,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,0,0,1,
1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,0,0,0,0,0,1,0,0,0,
1,0,0,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,
0,0,1,1,0,0,0,0,1,1,0,1,1,0,0,0,0,1,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0,1,0,0,1,0,1,
1,0,1,0,0,1,0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,0,0,0,0,1,0,1,1,0,0,1,0,1,0,0,0,
1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,
0,0,0,0,0,1,0,0,0,0,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,0,0,0,1,1,0,0,
1,0,1,1,0,0,0,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,0,0,0,1,0,0,0,0,1,1,0,0,
0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,0,0,1,1,0,0,0,0,1,1,0,1,1,0,0,0,0,0,1,0,0,0,0,1,
1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,
0,0,0,1,0,1,0,0,1,0,0,1,0,0,0,1,0,0,1,0,0,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,
1,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,0,0,0,1,0,0,0,
1,0,1,1,0,1,0,0,0,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,0,0,0,1,0,1,1,0,1,
0,0,0,1,0,0,0,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,0,1,
1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,0,0,0,1,0,0,1,
1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,
1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,
0,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,0,0,0,1,0,1,
0,0,1,0,0,0,0,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,0,1,0,0,1,0,0,
1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,1,
1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,0,1,0,0,0,1,0,1,1,0,1,
1,0,1,0,0,0,0,0,0,0,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,1,0,1,1,0,0,0,0,1,1,0,0,
1,0,1,0,0,1,0,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,0,0,1,
0,0,1,1,0,0,0,0,0,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,
0,0,0,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,0,1,
1,0,0,0,0,1,0,0,1,1,0,1,0,0,1,1,0,0,0,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,0,
1,0,1,0,0,1,0,0,0,1,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,
1,0,0,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,0,0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,
0,0,1,1,0,0,0,0,1,1,0,0,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,0,0,0,0,1,0,1,
1,0,1,1,0,0,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,0,0,0,1,0,0,1,0,1,0,0,0,
1,0,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,0,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,
0,0,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,0,0,0,0,1,0,0,
1,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,0,
0,0,1,0,0,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,0,1,0,0,0,0,1,
1,0,0,1,0,1,0,0,0,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,
1,0,0,1,0,0,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,1,
1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,0,0,0,1,0,0,0,
1,0,1,1,0,1,0,0,1,0,0,0,0,0,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,
0,0,1,1,0,0,0,0,1,1,0,1,1,0,0,0,0,0,1,0,0,0,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,
0,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,0,0,0,
1,0,0,1,0,0,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,
1,0,0,0,0,1,0,0,0,0,0,1,1,0,1,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,0,0,0,0,0,1,1,0,0,
1,0,1,1,0,0,0,0,1,0,0,1,0,0,0,0,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,0,0,0,1,1,0,1,
0,0,1,1,0,0,0,0,0,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,0,0,1,0,0,0,0,1,
1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,
0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,
1,0,0,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,0,0,0,0,1,0,0,
1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,1,
0,0,0,1,0,0,0,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,
1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,0,0,1,0,0,1,
0,0,0,1,0,1,0,0,0,1,0,0,0,0,1,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,0,0,1,0,0,1,
1,0,1,0,0,0,0,0,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,
0,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,
0,0,1,0,0,0,0,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,1,0,0,
1,0,1,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,1,
1,0,0,0,0,1,0,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,0,0,1,
1,0,1,0,0,0,0,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,0,0,0,0,0,1,1,0,0,
1,0,0,1,0,1,0,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,0,0,0,1,
0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,0,1,0,0,1,0,1,
0,0,1,1,0,1,0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,1,0,0,1,0,0,0,0,1,
1,0,0,0,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,
0,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,
1,0,0,1,0,0,0,0,1,0,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,0,1,0,0,0,0,0,0,1,0,1,1,0,0,
0,0,1,1,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,0,0,0,0,1,0,1,
1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,
1,0,0,1,0,1,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,
0,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,0,0,0,0,
1,0,1,0,0,1,0,0,0,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,0,0,0,1,0,1,1,0,0,
0,0,0,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,0,0,1,0,0,1,0,0,0,1,0,0,1,0,1,
1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,0,0,0,0,1,0,1,0,0,1,
1,0,0,1,0,0,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,
1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,0,0,0,0,0,1,1,0,0,1,0,1,1,0,0,1,0,0,0,0,1,0,0,0,
0,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,0,0,1,1,0,1,
0,0,1,1,0,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,0,
1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,1,0,0,0,
1,0,0,1,0,1,0,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,0,1,1,0,1,
1,0,0,0,0,1,0,0,0,0,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,1,0,1,0,0,0,0,0,1,1,0,0,
1,0,1,0,0,0,0,0,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,0,0,0,1,0,0,1,
0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,0,0,1,0,0,0,0,1,
1,0,0,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,0,1,
0,0,0,1,0,1,0,0,1,1,0,1,0,0,0,1,0,0,0,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,1,0,1,
1,0,1,0,0,1,0,0,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0,
1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,1,
0,0,0,1,0,0,0,0,1,0,0,0,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,0,0,0,0,1,0,1,
1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,0,0,1,0,0,0,
1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,0,0,0,1,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,
1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,0,0,0,1,1,0,0,
0,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,0,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,
0,0,1,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,0,1,0,0,0,0,0,
1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,0,0,0,1,0,1,0,0,1,
1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,0,0,1,0,0,1,0,0,0,1,0,0,1,0,1,
1,0,1,0,0,0,0,0,0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,0,0,0,1,1,0,0,
1,0,1,1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0,1,0,0,1,0,1,0,0,1,
0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,0,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,
0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,0,0,0,0,0,1
};
int pattern_size = (sizeof(pattern)/sizeof(pattern[0]));
SHAR_EOF
chmod 0444 pattern.c ||
echo 'restore of pattern.c failed'
Wc_c="`wc -c < 'pattern.c'`"
test 32129 -eq "$Wc_c" ||
	echo 'pattern.c: original size 32129, current size' "$Wc_c"
fi
# ============= pr_tbl.c ==============
if test -f 'pr_tbl.c' -a X"$1" != X"-c"; then
	echo 'x - skipping pr_tbl.c (File already exists)'
else
echo 'x - extracting pr_tbl.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'pr_tbl.c' &&
/*
X * Copyright (c) 1989 The Regents of the University of California.
X * All rights reserved.
X *
X * This code is derived from software contributed to Berkeley by
X * Landon Curt Noll.
X *
X * Redistribution and use in source and binary forms are permitted
X * provided that: (1) source distributions retain this entire copyright
X * notice and comment, and (2) distributions including binaries display
X * the following acknowledgement:  ``This product includes software
X * developed by the University of California, Berkeley and its contributors''
X * in the documentation or other materials provided with the distribution
X * and in all advertising materials mentioning features or use of this
X * software. Neither the name of the University nor the names of its
X * contributors may be used to endorse or promote products derived
X * from this software without specific prior written permission.
X * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
X * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
X * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
X */
X
#ifndef lint
static char sccsid[] = "@(#)pr_tbl.c	5.2 (Berkeley) 6/1/90";
#endif /* not lint */
X
/*
X * prime - prime table
X *
X * By: Landon Curt Noll   chongo@toad.com,   ...!{sun,tolsoft}!hoptoad!chongo
X *
X *   chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
X *
X * We are able to sieve 2^32-1 because this table has primes up to 65537 
X * and 65537^2 > 2^32-1.
X */
X
#include "primes.h"
X
ubig prime[] = {
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,
107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,
211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,
317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,
439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,
569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,
677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,
821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,
947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,
1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,
1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,
1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,
1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,
1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,
1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,
1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,
1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,
1973,1979,1987,1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,2063,2069,
2081,2083,2087,2089,2099,2111,2113,2129,2131,2137,2141,2143,2153,2161,2179,
2203,2207,2213,2221,2237,2239,2243,2251,2267,2269,2273,2281,2287,2293,2297,
2309,2311,2333,2339,2341,2347,2351,2357,2371,2377,2381,2383,2389,2393,2399,
2411,2417,2423,2437,2441,2447,2459,2467,2473,2477,2503,2521,2531,2539,2543,
2549,2551,2557,2579,2591,2593,2609,2617,2621,2633,2647,2657,2659,2663,2671,
2677,2683,2687,2689,2693,2699,2707,2711,2713,2719,2729,2731,2741,2749,2753,
2767,2777,2789,2791,2797,2801,2803,2819,2833,2837,2843,2851,2857,2861,2879,
2887,2897,2903,2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,3001,3011,
3019,3023,3037,3041,3049,3061,3067,3079,3083,3089,3109,3119,3121,3137,3163,
3167,3169,3181,3187,3191,3203,3209,3217,3221,3229,3251,3253,3257,3259,3271,
3299,3301,3307,3313,3319,3323,3329,3331,3343,3347,3359,3361,3371,3373,3389,
3391,3407,3413,3433,3449,3457,3461,3463,3467,3469,3491,3499,3511,3517,3527,
3529,3533,3539,3541,3547,3557,3559,3571,3581,3583,3593,3607,3613,3617,3623,
3631,3637,3643,3659,3671,3673,3677,3691,3697,3701,3709,3719,3727,3733,3739,
3761,3767,3769,3779,3793,3797,3803,3821,3823,3833,3847,3851,3853,3863,3877,
3881,3889,3907,3911,3917,3919,3923,3929,3931,3943,3947,3967,3989,4001,4003,
4007,4013,4019,4021,4027,4049,4051,4057,4073,4079,4091,4093,4099,4111,4127,
4129,4133,4139,4153,4157,4159,4177,4201,4211,4217,4219,4229,4231,4241,4243,
4253,4259,4261,4271,4273,4283,4289,4297,4327,4337,4339,4349,4357,4363,4373,
4391,4397,4409,4421,4423,4441,4447,4451,4457,4463,4481,4483,4493,4507,4513,
4517,4519,4523,4547,4549,4561,4567,4583,4591,4597,4603,4621,4637,4639,4643,
4649,4651,4657,4663,4673,4679,4691,4703,4721,4723,4729,4733,4751,4759,4783,
4787,4789,4793,4799,4801,4813,4817,4831,4861,4871,4877,4889,4903,4909,4919,
4931,4933,4937,4943,4951,4957,4967,4969,4973,4987,4993,4999,5003,5009,5011,
5021,5023,5039,5051,5059,5077,5081,5087,5099,5101,5107,5113,5119,5147,5153,
5167,5171,5179,5189,5197,5209,5227,5231,5233,5237,5261,5273,5279,5281,5297,
5303,5309,5323,5333,5347,5351,5381,5387,5393,5399,5407,5413,5417,5419,5431,
5437,5441,5443,5449,5471,5477,5479,5483,5501,5503,5507,5519,5521,5527,5531,
5557,5563,5569,5573,5581,5591,5623,5639,5641,5647,5651,5653,5657,5659,5669,
5683,5689,5693,5701,5711,5717,5737,5741,5743,5749,5779,5783,5791,5801,5807,
5813,5821,5827,5839,5843,5849,5851,5857,5861,5867,5869,5879,5881,5897,5903,
5923,5927,5939,5953,5981,5987,6007,6011,6029,6037,6043,6047,6053,6067,6073,
6079,6089,6091,6101,6113,6121,6131,6133,6143,6151,6163,6173,6197,6199,6203,
6211,6217,6221,6229,6247,6257,6263,6269,6271,6277,6287,6299,6301,6311,6317,
6323,6329,6337,6343,6353,6359,6361,6367,6373,6379,6389,6397,6421,6427,6449,
6451,6469,6473,6481,6491,6521,6529,6547,6551,6553,6563,6569,6571,6577,6581,
6599,6607,6619,6637,6653,6659,6661,6673,6679,6689,6691,6701,6703,6709,6719,
6733,6737,6761,6763,6779,6781,6791,6793,6803,6823,6827,6829,6833,6841,6857,
6863,6869,6871,6883,6899,6907,6911,6917,6947,6949,6959,6961,6967,6971,6977,
6983,6991,6997,7001,7013,7019,7027,7039,7043,7057,7069,7079,7103,7109,7121,
7127,7129,7151,7159,7177,7187,7193,7207,7211,7213,7219,7229,7237,7243,7247,
7253,7283,7297,7307,7309,7321,7331,7333,7349,7351,7369,7393,7411,7417,7433,
7451,7457,7459,7477,7481,7487,7489,7499,7507,7517,7523,7529,7537,7541,7547,
7549,7559,7561,7573,7577,7583,7589,7591,7603,7607,7621,7639,7643,7649,7669,
7673,7681,7687,7691,7699,7703,7717,7723,7727,7741,7753,7757,7759,7789,7793,
7817,7823,7829,7841,7853,7867,7873,7877,7879,7883,7901,7907,7919,7927,7933,
7937,7949,7951,7963,7993,8009,8011,8017,8039,8053,8059,8069,8081,8087,8089,
8093,8101,8111,8117,8123,8147,8161,8167,8171,8179,8191,8209,8219,8221,8231,
8233,8237,8243,8263,8269,8273,8287,8291,8293,8297,8311,8317,8329,8353,8363,
8369,8377,8387,8389,8419,8423,8429,8431,8443,8447,8461,8467,8501,8513,8521,
8527,8537,8539,8543,8563,8573,8581,8597,8599,8609,8623,8627,8629,8641,8647,
8663,8669,8677,8681,8689,8693,8699,8707,8713,8719,8731,8737,8741,8747,8753,
8761,8779,8783,8803,8807,8819,8821,8831,8837,8839,8849,8861,8863,8867,8887,
8893,8923,8929,8933,8941,8951,8963,8969,8971,8999,9001,9007,9011,9013,9029,
9041,9043,9049,9059,9067,9091,9103,9109,9127,9133,9137,9151,9157,9161,9173,
9181,9187,9199,9203,9209,9221,9227,9239,9241,9257,9277,9281,9283,9293,9311,
9319,9323,9337,9341,9343,9349,9371,9377,9391,9397,9403,9413,9419,9421,9431,
9433,9437,9439,9461,9463,9467,9473,9479,9491,9497,9511,9521,9533,9539,9547,
9551,9587,9601,9613,9619,9623,9629,9631,9643,9649,9661,9677,9679,9689,9697,
9719,9721,9733,9739,9743,9749,9767,9769,9781,9787,9791,9803,9811,9817,9829,
9833,9839,9851,9857,9859,9871,9883,9887,9901,9907,9923,9929,9931,9941,9949,
9967,9973,10007,10009,10037,10039,10061,10067,10069,10079,10091,10093,10099,
10103,10111,10133,10139,10141,10151,10159,10163,10169,10177,10181,10193,10211,
10223,10243,10247,10253,10259,10267,10271,10273,10289,10301,10303,10313,10321,
10331,10333,10337,10343,10357,10369,10391,10399,10427,10429,10433,10453,10457,
10459,10463,10477,10487,10499,10501,10513,10529,10531,10559,10567,10589,10597,
10601,10607,10613,10627,10631,10639,10651,10657,10663,10667,10687,10691,10709,
10711,10723,10729,10733,10739,10753,10771,10781,10789,10799,10831,10837,10847,
10853,10859,10861,10867,10883,10889,10891,10903,10909,10937,10939,10949,10957,
10973,10979,10987,10993,11003,11027,11047,11057,11059,11069,11071,11083,11087,
11093,11113,11117,11119,11131,11149,11159,11161,11171,11173,11177,11197,11213,
11239,11243,11251,11257,11261,11273,11279,11287,11299,11311,11317,11321,11329,
11351,11353,11369,11383,11393,11399,11411,11423,11437,11443,11447,11467,11471,
11483,11489,11491,11497,11503,11519,11527,11549,11551,11579,11587,11593,11597,
11617,11621,11633,11657,11677,11681,11689,11699,11701,11717,11719,11731,11743,
11777,11779,11783,11789,11801,11807,11813,11821,11827,11831,11833,11839,11863,
11867,11887,11897,11903,11909,11923,11927,11933,11939,11941,11953,11959,11969,
11971,11981,11987,12007,12011,12037,12041,12043,12049,12071,12073,12097,12101,
12107,12109,12113,12119,12143,12149,12157,12161,12163,12197,12203,12211,12227,
12239,12241,12251,12253,12263,12269,12277,12281,12289,12301,12323,12329,12343,
12347,12373,12377,12379,12391,12401,12409,12413,12421,12433,12437,12451,12457,
12473,12479,12487,12491,12497,12503,12511,12517,12527,12539,12541,12547,12553,
12569,12577,12583,12589,12601,12611,12613,12619,12637,12641,12647,12653,12659,
12671,12689,12697,12703,12713,12721,12739,12743,12757,12763,12781,12791,12799,
12809,12821,12823,12829,12841,12853,12889,12893,12899,12907,12911,12917,12919,
12923,12941,12953,12959,12967,12973,12979,12983,13001,13003,13007,13009,13033,
13037,13043,13049,13063,13093,13099,13103,13109,13121,13127,13147,13151,13159,
13163,13171,13177,13183,13187,13217,13219,13229,13241,13249,13259,13267,13291,
13297,13309,13313,13327,13331,13337,13339,13367,13381,13397,13399,13411,13417,
13421,13441,13451,13457,13463,13469,13477,13487,13499,13513,13523,13537,13553,
13567,13577,13591,13597,13613,13619,13627,13633,13649,13669,13679,13681,13687,
13691,13693,13697,13709,13711,13721,13723,13729,13751,13757,13759,13763,13781,
13789,13799,13807,13829,13831,13841,13859,13873,13877,13879,13883,13901,13903,
13907,13913,13921,13931,13933,13963,13967,13997,13999,14009,14011,14029,14033,
14051,14057,14071,14081,14083,14087,14107,14143,14149,14153,14159,14173,14177,
14197,14207,14221,14243,14249,14251,14281,14293,14303,14321,14323,14327,14341,
14347,14369,14387,14389,14401,14407,14411,14419,14423,14431,14437,14447,14449,
14461,14479,14489,14503,14519,14533,14537,14543,14549,14551,14557,14561,14563,
14591,14593,14621,14627,14629,14633,14639,14653,14657,14669,14683,14699,14713,
14717,14723,14731,14737,14741,14747,14753,14759,14767,14771,14779,14783,14797,
14813,14821,14827,14831,14843,14851,14867,14869,14879,14887,14891,14897,14923,
14929,14939,14947,14951,14957,14969,14983,15013,15017,15031,15053,15061,15073,
15077,15083,15091,15101,15107,15121,15131,15137,15139,15149,15161,15173,15187,
15193,15199,15217,15227,15233,15241,15259,15263,15269,15271,15277,15287,15289,
15299,15307,15313,15319,15329,15331,15349,15359,15361,15373,15377,15383,15391,
15401,15413,15427,15439,15443,15451,15461,15467,15473,15493,15497,15511,15527,
15541,15551,15559,15569,15581,15583,15601,15607,15619,15629,15641,15643,15647,
15649,15661,15667,15671,15679,15683,15727,15731,15733,15737,15739,15749,15761,
15767,15773,15787,15791,15797,15803,15809,15817,15823,15859,15877,15881,15887,
15889,15901,15907,15913,15919,15923,15937,15959,15971,15973,15991,16001,16007,
16033,16057,16061,16063,16067,16069,16073,16087,16091,16097,16103,16111,16127,
16139,16141,16183,16187,16189,16193,16217,16223,16229,16231,16249,16253,16267,
16273,16301,16319,16333,16339,16349,16361,16363,16369,16381,16411,16417,16421,
16427,16433,16447,16451,16453,16477,16481,16487,16493,16519,16529,16547,16553,
16561,16567,16573,16603,16607,16619,16631,16633,16649,16651,16657,16661,16673,
16691,16693,16699,16703,16729,16741,16747,16759,16763,16787,16811,16823,16829,
16831,16843,16871,16879,16883,16889,16901,16903,16921,16927,16931,16937,16943,
16963,16979,16981,16987,16993,17011,17021,17027,17029,17033,17041,17047,17053,
17077,17093,17099,17107,17117,17123,17137,17159,17167,17183,17189,17191,17203,
17207,17209,17231,17239,17257,17291,17293,17299,17317,17321,17327,17333,17341,
17351,17359,17377,17383,17387,17389,17393,17401,17417,17419,17431,17443,17449,
17467,17471,17477,17483,17489,17491,17497,17509,17519,17539,17551,17569,17573,
17579,17581,17597,17599,17609,17623,17627,17657,17659,17669,17681,17683,17707,
17713,17729,17737,17747,17749,17761,17783,17789,17791,17807,17827,17837,17839,
17851,17863,17881,17891,17903,17909,17911,17921,17923,17929,17939,17957,17959,
17971,17977,17981,17987,17989,18013,18041,18043,18047,18049,18059,18061,18077,
18089,18097,18119,18121,18127,18131,18133,18143,18149,18169,18181,18191,18199,
18211,18217,18223,18229,18233,18251,18253,18257,18269,18287,18289,18301,18307,
18311,18313,18329,18341,18353,18367,18371,18379,18397,18401,18413,18427,18433,
18439,18443,18451,18457,18461,18481,18493,18503,18517,18521,18523,18539,18541,
18553,18583,18587,18593,18617,18637,18661,18671,18679,18691,18701,18713,18719,
18731,18743,18749,18757,18773,18787,18793,18797,18803,18839,18859,18869,18899,
18911,18913,18917,18919,18947,18959,18973,18979,19001,19009,19013,19031,19037,
19051,19069,19073,19079,19081,19087,19121,19139,19141,19157,19163,19181,19183,
19207,19211,19213,19219,19231,19237,19249,19259,19267,19273,19289,19301,19309,
19319,19333,19373,19379,19381,19387,19391,19403,19417,19421,19423,19427,19429,
19433,19441,19447,19457,19463,19469,19471,19477,19483,19489,19501,19507,19531,
19541,19543,19553,19559,19571,19577,19583,19597,19603,19609,19661,19681,19687,
19697,19699,19709,19717,19727,19739,19751,19753,19759,19763,19777,19793,19801,
19813,19819,19841,19843,19853,19861,19867,19889,19891,19913,19919,19927,19937,
19949,19961,19963,19973,19979,19991,19993,19997,20011,20021,20023,20029,20047,
20051,20063,20071,20089,20101,20107,20113,20117,20123,20129,20143,20147,20149,
20161,20173,20177,20183,20201,20219,20231,20233,20249,20261,20269,20287,20297,
20323,20327,20333,20341,20347,20353,20357,20359,20369,20389,20393,20399,20407,
20411,20431,20441,20443,20477,20479,20483,20507,20509,20521,20533,20543,20549,
20551,20563,20593,20599,20611,20627,20639,20641,20663,20681,20693,20707,20717,
20719,20731,20743,20747,20749,20753,20759,20771,20773,20789,20807,20809,20849,
20857,20873,20879,20887,20897,20899,20903,20921,20929,20939,20947,20959,20963,
20981,20983,21001,21011,21013,21017,21019,21023,21031,21059,21061,21067,21089,
21101,21107,21121,21139,21143,21149,21157,21163,21169,21179,21187,21191,21193,
21211,21221,21227,21247,21269,21277,21283,21313,21317,21319,21323,21341,21347,
21377,21379,21383,21391,21397,21401,21407,21419,21433,21467,21481,21487,21491,
21493,21499,21503,21517,21521,21523,21529,21557,21559,21563,21569,21577,21587,
21589,21599,21601,21611,21613,21617,21647,21649,21661,21673,21683,21701,21713,
21727,21737,21739,21751,21757,21767,21773,21787,21799,21803,21817,21821,21839,
21841,21851,21859,21863,21871,21881,21893,21911,21929,21937,21943,21961,21977,
21991,21997,22003,22013,22027,22031,22037,22039,22051,22063,22067,22073,22079,
22091,22093,22109,22111,22123,22129,22133,22147,22153,22157,22159,22171,22189,
22193,22229,22247,22259,22271,22273,22277,22279,22283,22291,22303,22307,22343,
22349,22367,22369,22381,22391,22397,22409,22433,22441,22447,22453,22469,22481,
22483,22501,22511,22531,22541,22543,22549,22567,22571,22573,22613,22619,22621,
22637,22639,22643,22651,22669,22679,22691,22697,22699,22709,22717,22721,22727,
22739,22741,22751,22769,22777,22783,22787,22807,22811,22817,22853,22859,22861,
22871,22877,22901,22907,22921,22937,22943,22961,22963,22973,22993,23003,23011,
23017,23021,23027,23029,23039,23041,23053,23057,23059,23063,23071,23081,23087,
23099,23117,23131,23143,23159,23167,23173,23189,23197,23201,23203,23209,23227,
23251,23269,23279,23291,23293,23297,23311,23321,23327,23333,23339,23357,23369,
23371,23399,23417,23431,23447,23459,23473,23497,23509,23531,23537,23539,23549,
23557,23561,23563,23567,23581,23593,23599,23603,23609,23623,23627,23629,23633,
23663,23669,23671,23677,23687,23689,23719,23741,23743,23747,23753,23761,23767,
23773,23789,23801,23813,23819,23827,23831,23833,23857,23869,23873,23879,23887,
23893,23899,23909,23911,23917,23929,23957,23971,23977,23981,23993,24001,24007,
24019,24023,24029,24043,24049,24061,24071,24077,24083,24091,24097,24103,24107,
24109,24113,24121,24133,24137,24151,24169,24179,24181,24197,24203,24223,24229,
24239,24247,24251,24281,24317,24329,24337,24359,24371,24373,24379,24391,24407,
24413,24419,24421,24439,24443,24469,24473,24481,24499,24509,24517,24527,24533,
24547,24551,24571,24593,24611,24623,24631,24659,24671,24677,24683,24691,24697,
24709,24733,24749,24763,24767,24781,24793,24799,24809,24821,24841,24847,24851,
24859,24877,24889,24907,24917,24919,24923,24943,24953,24967,24971,24977,24979,
24989,25013,25031,25033,25037,25057,25073,25087,25097,25111,25117,25121,25127,
25147,25153,25163,25169,25171,25183,25189,25219,25229,25237,25243,25247,25253,
25261,25301,25303,25307,25309,25321,25339,25343,25349,25357,25367,25373,25391,
25409,25411,25423,25439,25447,25453,25457,25463,25469,25471,25523,25537,25541,
25561,25577,25579,25583,25589,25601,25603,25609,25621,25633,25639,25643,25657,
25667,25673,25679,25693,25703,25717,25733,25741,25747,25759,25763,25771,25793,
25799,25801,25819,25841,25847,25849,25867,25873,25889,25903,25913,25919,25931,
25933,25939,25943,25951,25969,25981,25997,25999,26003,26017,26021,26029,26041,
26053,26083,26099,26107,26111,26113,26119,26141,26153,26161,26171,26177,26183,
26189,26203,26209,26227,26237,26249,26251,26261,26263,26267,26293,26297,26309,
26317,26321,26339,26347,26357,26371,26387,26393,26399,26407,26417,26423,26431,
26437,26449,26459,26479,26489,26497,26501,26513,26539,26557,26561,26573,26591,
26597,26627,26633,26641,26647,26669,26681,26683,26687,26693,26699,26701,26711,
26713,26717,26723,26729,26731,26737,26759,26777,26783,26801,26813,26821,26833,
26839,26849,26861,26863,26879,26881,26891,26893,26903,26921,26927,26947,26951,
26953,26959,26981,26987,26993,27011,27017,27031,27043,27059,27061,27067,27073,
27077,27091,27103,27107,27109,27127,27143,27179,27191,27197,27211,27239,27241,
27253,27259,27271,27277,27281,27283,27299,27329,27337,27361,27367,27397,27407,
27409,27427,27431,27437,27449,27457,27479,27481,27487,27509,27527,27529,27539,
27541,27551,27581,27583,27611,27617,27631,27647,27653,27673,27689,27691,27697,
27701,27733,27737,27739,27743,27749,27751,27763,27767,27773,27779,27791,27793,
27799,27803,27809,27817,27823,27827,27847,27851,27883,27893,27901,27917,27919,
27941,27943,27947,27953,27961,27967,27983,27997,28001,28019,28027,28031,28051,
28057,28069,28081,28087,28097,28099,28109,28111,28123,28151,28163,28181,28183,
28201,28211,28219,28229,28277,28279,28283,28289,28297,28307,28309,28319,28349,
28351,28387,28393,28403,28409,28411,28429,28433,28439,28447,28463,28477,28493,
28499,28513,28517,28537,28541,28547,28549,28559,28571,28573,28579,28591,28597,
28603,28607,28619,28621,28627,28631,28643,28649,28657,28661,28663,28669,28687,
28697,28703,28711,28723,28729,28751,28753,28759,28771,28789,28793,28807,28813,
28817,28837,28843,28859,28867,28871,28879,28901,28909,28921,28927,28933,28949,
28961,28979,29009,29017,29021,29023,29027,29033,29059,29063,29077,29101,29123,
29129,29131,29137,29147,29153,29167,29173,29179,29191,29201,29207,29209,29221,
29231,29243,29251,29269,29287,29297,29303,29311,29327,29333,29339,29347,29363,
29383,29387,29389,29399,29401,29411,29423,29429,29437,29443,29453,29473,29483,
29501,29527,29531,29537,29567,29569,29573,29581,29587,29599,29611,29629,29633,
29641,29663,29669,29671,29683,29717,29723,29741,29753,29759,29761,29789,29803,
29819,29833,29837,29851,29863,29867,29873,29879,29881,29917,29921,29927,29947,
29959,29983,29989,30011,30013,30029,30047,30059,30071,30089,30091,30097,30103,
30109,30113,30119,30133,30137,30139,30161,30169,30181,30187,30197,30203,30211,
30223,30241,30253,30259,30269,30271,30293,30307,30313,30319,30323,30341,30347,
30367,30389,30391,30403,30427,30431,30449,30467,30469,30491,30493,30497,30509,
30517,30529,30539,30553,30557,30559,30577,30593,30631,30637,30643,30649,30661,
30671,30677,30689,30697,30703,30707,30713,30727,30757,30763,30773,30781,30803,
30809,30817,30829,30839,30841,30851,30853,30859,30869,30871,30881,30893,30911,
30931,30937,30941,30949,30971,30977,30983,31013,31019,31033,31039,31051,31063,
31069,31079,31081,31091,31121,31123,31139,31147,31151,31153,31159,31177,31181,
31183,31189,31193,31219,31223,31231,31237,31247,31249,31253,31259,31267,31271,
31277,31307,31319,31321,31327,31333,31337,31357,31379,31387,31391,31393,31397,
31469,31477,31481,31489,31511,31513,31517,31531,31541,31543,31547,31567,31573,
31583,31601,31607,31627,31643,31649,31657,31663,31667,31687,31699,31721,31723,
31727,31729,31741,31751,31769,31771,31793,31799,31817,31847,31849,31859,31873,
31883,31891,31907,31957,31963,31973,31981,31991,32003,32009,32027,32029,32051,
32057,32059,32063,32069,32077,32083,32089,32099,32117,32119,32141,32143,32159,
32173,32183,32189,32191,32203,32213,32233,32237,32251,32257,32261,32297,32299,
32303,32309,32321,32323,32327,32341,32353,32359,32363,32369,32371,32377,32381,
32401,32411,32413,32423,32429,32441,32443,32467,32479,32491,32497,32503,32507,
32531,32533,32537,32561,32563,32569,32573,32579,32587,32603,32609,32611,32621,
32633,32647,32653,32687,32693,32707,32713,32717,32719,32749,32771,32779,32783,
32789,32797,32801,32803,32831,32833,32839,32843,32869,32887,32909,32911,32917,
32933,32939,32941,32957,32969,32971,32983,32987,32993,32999,33013,33023,33029,
33037,33049,33053,33071,33073,33083,33091,33107,33113,33119,33149,33151,33161,
33179,33181,33191,33199,33203,33211,33223,33247,33287,33289,33301,33311,33317,
33329,33331,33343,33347,33349,33353,33359,33377,33391,33403,33409,33413,33427,
33457,33461,33469,33479,33487,33493,33503,33521,33529,33533,33547,33563,33569,
33577,33581,33587,33589,33599,33601,33613,33617,33619,33623,33629,33637,33641,
33647,33679,33703,33713,33721,33739,33749,33751,33757,33767,33769,33773,33791,
33797,33809,33811,33827,33829,33851,33857,33863,33871,33889,33893,33911,33923,
33931,33937,33941,33961,33967,33997,34019,34031,34033,34039,34057,34061,34123,
34127,34129,34141,34147,34157,34159,34171,34183,34211,34213,34217,34231,34253,
34259,34261,34267,34273,34283,34297,34301,34303,34313,34319,34327,34337,34351,
34361,34367,34369,34381,34403,34421,34429,34439,34457,34469,34471,34483,34487,
34499,34501,34511,34513,34519,34537,34543,34549,34583,34589,34591,34603,34607,
34613,34631,34649,34651,34667,34673,34679,34687,34693,34703,34721,34729,34739,
34747,34757,34759,34763,34781,34807,34819,34841,34843,34847,34849,34871,34877,
34883,34897,34913,34919,34939,34949,34961,34963,34981,35023,35027,35051,35053,
35059,35069,35081,35083,35089,35099,35107,35111,35117,35129,35141,35149,35153,
35159,35171,35201,35221,35227,35251,35257,35267,35279,35281,35291,35311,35317,
35323,35327,35339,35353,35363,35381,35393,35401,35407,35419,35423,35437,35447,
35449,35461,35491,35507,35509,35521,35527,35531,35533,35537,35543,35569,35573,
35591,35593,35597,35603,35617,35671,35677,35729,35731,35747,35753,35759,35771,
35797,35801,35803,35809,35831,35837,35839,35851,35863,35869,35879,35897,35899,
35911,35923,35933,35951,35963,35969,35977,35983,35993,35999,36007,36011,36013,
36017,36037,36061,36067,36073,36083,36097,36107,36109,36131,36137,36151,36161,
36187,36191,36209,36217,36229,36241,36251,36263,36269,36277,36293,36299,36307,
36313,36319,36341,36343,36353,36373,36383,36389,36433,36451,36457,36467,36469,
36473,36479,36493,36497,36523,36527,36529,36541,36551,36559,36563,36571,36583,
36587,36599,36607,36629,36637,36643,36653,36671,36677,36683,36691,36697,36709,
36713,36721,36739,36749,36761,36767,36779,36781,36787,36791,36793,36809,36821,
36833,36847,36857,36871,36877,36887,36899,36901,36913,36919,36923,36929,36931,
36943,36947,36973,36979,36997,37003,37013,37019,37021,37039,37049,37057,37061,
37087,37097,37117,37123,37139,37159,37171,37181,37189,37199,37201,37217,37223,
37243,37253,37273,37277,37307,37309,37313,37321,37337,37339,37357,37361,37363,
37369,37379,37397,37409,37423,37441,37447,37463,37483,37489,37493,37501,37507,
37511,37517,37529,37537,37547,37549,37561,37567,37571,37573,37579,37589,37591,
37607,37619,37633,37643,37649,37657,37663,37691,37693,37699,37717,37747,37781,
37783,37799,37811,37813,37831,37847,37853,37861,37871,37879,37889,37897,37907,
37951,37957,37963,37967,37987,37991,37993,37997,38011,38039,38047,38053,38069,
38083,38113,38119,38149,38153,38167,38177,38183,38189,38197,38201,38219,38231,
38237,38239,38261,38273,38281,38287,38299,38303,38317,38321,38327,38329,38333,
38351,38371,38377,38393,38431,38447,38449,38453,38459,38461,38501,38543,38557,
38561,38567,38569,38593,38603,38609,38611,38629,38639,38651,38653,38669,38671,
38677,38693,38699,38707,38711,38713,38723,38729,38737,38747,38749,38767,38783,
38791,38803,38821,38833,38839,38851,38861,38867,38873,38891,38903,38917,38921,
38923,38933,38953,38959,38971,38977,38993,39019,39023,39041,39043,39047,39079,
39089,39097,39103,39107,39113,39119,39133,39139,39157,39161,39163,39181,39191,
39199,39209,39217,39227,39229,39233,39239,39241,39251,39293,39301,39313,39317,
39323,39341,39343,39359,39367,39371,39373,39383,39397,39409,39419,39439,39443,
39451,39461,39499,39503,39509,39511,39521,39541,39551,39563,39569,39581,39607,
39619,39623,39631,39659,39667,39671,39679,39703,39709,39719,39727,39733,39749,
39761,39769,39779,39791,39799,39821,39827,39829,39839,39841,39847,39857,39863,
39869,39877,39883,39887,39901,39929,39937,39953,39971,39979,39983,39989,40009,
40013,40031,40037,40039,40063,40087,40093,40099,40111,40123,40127,40129,40151,
40153,40163,40169,40177,40189,40193,40213,40231,40237,40241,40253,40277,40283,
40289,40343,40351,40357,40361,40387,40423,40427,40429,40433,40459,40471,40483,
40487,40493,40499,40507,40519,40529,40531,40543,40559,40577,40583,40591,40597,
40609,40627,40637,40639,40693,40697,40699,40709,40739,40751,40759,40763,40771,
40787,40801,40813,40819,40823,40829,40841,40847,40849,40853,40867,40879,40883,
40897,40903,40927,40933,40939,40949,40961,40973,40993,41011,41017,41023,41039,
41047,41051,41057,41077,41081,41113,41117,41131,41141,41143,41149,41161,41177,
41179,41183,41189,41201,41203,41213,41221,41227,41231,41233,41243,41257,41263,
41269,41281,41299,41333,41341,41351,41357,41381,41387,41389,41399,41411,41413,
41443,41453,41467,41479,41491,41507,41513,41519,41521,41539,41543,41549,41579,
41593,41597,41603,41609,41611,41617,41621,41627,41641,41647,41651,41659,41669,
41681,41687,41719,41729,41737,41759,41761,41771,41777,41801,41809,41813,41843,
41849,41851,41863,41879,41887,41893,41897,41903,41911,41927,41941,41947,41953,
41957,41959,41969,41981,41983,41999,42013,42017,42019,42023,42043,42061,42071,
42073,42083,42089,42101,42131,42139,42157,42169,42179,42181,42187,42193,42197,
42209,42221,42223,42227,42239,42257,42281,42283,42293,42299,42307,42323,42331,
42337,42349,42359,42373,42379,42391,42397,42403,42407,42409,42433,42437,42443,
42451,42457,42461,42463,42467,42473,42487,42491,42499,42509,42533,42557,42569,
42571,42577,42589,42611,42641,42643,42649,42667,42677,42683,42689,42697,42701,
42703,42709,42719,42727,42737,42743,42751,42767,42773,42787,42793,42797,42821,
42829,42839,42841,42853,42859,42863,42899,42901,42923,42929,42937,42943,42953,
42961,42967,42979,42989,43003,43013,43019,43037,43049,43051,43063,43067,43093,
43103,43117,43133,43151,43159,43177,43189,43201,43207,43223,43237,43261,43271,
43283,43291,43313,43319,43321,43331,43391,43397,43399,43403,43411,43427,43441,
43451,43457,43481,43487,43499,43517,43541,43543,43573,43577,43579,43591,43597,
43607,43609,43613,43627,43633,43649,43651,43661,43669,43691,43711,43717,43721,
43753,43759,43777,43781,43783,43787,43789,43793,43801,43853,43867,43889,43891,
43913,43933,43943,43951,43961,43963,43969,43973,43987,43991,43997,44017,44021,
44027,44029,44041,44053,44059,44071,44087,44089,44101,44111,44119,44123,44129,
44131,44159,44171,44179,44189,44201,44203,44207,44221,44249,44257,44263,44267,
44269,44273,44279,44281,44293,44351,44357,44371,44381,44383,44389,44417,44449,
44453,44483,44491,44497,44501,44507,44519,44531,44533,44537,44543,44549,44563,
44579,44587,44617,44621,44623,44633,44641,44647,44651,44657,44683,44687,44699,
44701,44711,44729,44741,44753,44771,44773,44777,44789,44797,44809,44819,44839,
44843,44851,44867,44879,44887,44893,44909,44917,44927,44939,44953,44959,44963,
44971,44983,44987,45007,45013,45053,45061,45077,45083,45119,45121,45127,45131,
45137,45139,45161,45179,45181,45191,45197,45233,45247,45259,45263,45281,45289,
45293,45307,45317,45319,45329,45337,45341,45343,45361,45377,45389,45403,45413,
45427,45433,45439,45481,45491,45497,45503,45523,45533,45541,45553,45557,45569,
45587,45589,45599,45613,45631,45641,45659,45667,45673,45677,45691,45697,45707,
45737,45751,45757,45763,45767,45779,45817,45821,45823,45827,45833,45841,45853,
45863,45869,45887,45893,45943,45949,45953,45959,45971,45979,45989,46021,46027,
46049,46051,46061,46073,46091,46093,46099,46103,46133,46141,46147,46153,46171,
46181,46183,46187,46199,46219,46229,46237,46261,46271,46273,46279,46301,46307,
46309,46327,46337,46349,46351,46381,46399,46411,46439,46441,46447,46451,46457,
46471,46477,46489,46499,46507,46511,46523,46549,46559,46567,46573,46589,46591,
46601,46619,46633,46639,46643,46649,46663,46679,46681,46687,46691,46703,46723,
46727,46747,46751,46757,46769,46771,46807,46811,46817,46819,46829,46831,46853,
46861,46867,46877,46889,46901,46919,46933,46957,46993,46997,47017,47041,47051,
47057,47059,47087,47093,47111,47119,47123,47129,47137,47143,47147,47149,47161,
47189,47207,47221,47237,47251,47269,47279,47287,47293,47297,47303,47309,47317,
47339,47351,47353,47363,47381,47387,47389,47407,47417,47419,47431,47441,47459,
47491,47497,47501,47507,47513,47521,47527,47533,47543,47563,47569,47581,47591,
47599,47609,47623,47629,47639,47653,47657,47659,47681,47699,47701,47711,47713,
47717,47737,47741,47743,47777,47779,47791,47797,47807,47809,47819,47837,47843,
47857,47869,47881,47903,47911,47917,47933,47939,47947,47951,47963,47969,47977,
47981,48017,48023,48029,48049,48073,48079,48091,48109,48119,48121,48131,48157,
48163,48179,48187,48193,48197,48221,48239,48247,48259,48271,48281,48299,48311,
48313,48337,48341,48353,48371,48383,48397,48407,48409,48413,48437,48449,48463,
48473,48479,48481,48487,48491,48497,48523,48527,48533,48539,48541,48563,48571,
48589,48593,48611,48619,48623,48647,48649,48661,48673,48677,48679,48731,48733,
48751,48757,48761,48767,48779,48781,48787,48799,48809,48817,48821,48823,48847,
48857,48859,48869,48871,48883,48889,48907,48947,48953,48973,48989,48991,49003,
49009,49019,49031,49033,49037,49043,49057,49069,49081,49103,49109,49117,49121,
49123,49139,49157,49169,49171,49177,49193,49199,49201,49207,49211,49223,49253,
49261,49277,49279,49297,49307,49331,49333,49339,49363,49367,49369,49391,49393,
49409,49411,49417,49429,49433,49451,49459,49463,49477,49481,49499,49523,49529,
49531,49537,49547,49549,49559,49597,49603,49613,49627,49633,49639,49663,49667,
49669,49681,49697,49711,49727,49739,49741,49747,49757,49783,49787,49789,49801,
49807,49811,49823,49831,49843,49853,49871,49877,49891,49919,49921,49927,49937,
49939,49943,49957,49991,49993,49999,50021,50023,50033,50047,50051,50053,50069,
50077,50087,50093,50101,50111,50119,50123,50129,50131,50147,50153,50159,50177,
50207,50221,50227,50231,50261,50263,50273,50287,50291,50311,50321,50329,50333,
50341,50359,50363,50377,50383,50387,50411,50417,50423,50441,50459,50461,50497,
50503,50513,50527,50539,50543,50549,50551,50581,50587,50591,50593,50599,50627,
50647,50651,50671,50683,50707,50723,50741,50753,50767,50773,50777,50789,50821,
50833,50839,50849,50857,50867,50873,50891,50893,50909,50923,50929,50951,50957,
50969,50971,50989,50993,51001,51031,51043,51047,51059,51061,51071,51109,51131,
51133,51137,51151,51157,51169,51193,51197,51199,51203,51217,51229,51239,51241,
51257,51263,51283,51287,51307,51329,51341,51343,51347,51349,51361,51383,51407,
51413,51419,51421,51427,51431,51437,51439,51449,51461,51473,51479,51481,51487,
51503,51511,51517,51521,51539,51551,51563,51577,51581,51593,51599,51607,51613,
51631,51637,51647,51659,51673,51679,51683,51691,51713,51719,51721,51749,51767,
51769,51787,51797,51803,51817,51827,51829,51839,51853,51859,51869,51871,51893,
51899,51907,51913,51929,51941,51949,51971,51973,51977,51991,52009,52021,52027,
52051,52057,52067,52069,52081,52103,52121,52127,52147,52153,52163,52177,52181,
52183,52189,52201,52223,52237,52249,52253,52259,52267,52289,52291,52301,52313,
52321,52361,52363,52369,52379,52387,52391,52433,52453,52457,52489,52501,52511,
52517,52529,52541,52543,52553,52561,52567,52571,52579,52583,52609,52627,52631,
52639,52667,52673,52691,52697,52709,52711,52721,52727,52733,52747,52757,52769,
52783,52807,52813,52817,52837,52859,52861,52879,52883,52889,52901,52903,52919,
52937,52951,52957,52963,52967,52973,52981,52999,53003,53017,53047,53051,53069,
53077,53087,53089,53093,53101,53113,53117,53129,53147,53149,53161,53171,53173,
53189,53197,53201,53231,53233,53239,53267,53269,53279,53281,53299,53309,53323,
53327,53353,53359,53377,53381,53401,53407,53411,53419,53437,53441,53453,53479,
53503,53507,53527,53549,53551,53569,53591,53593,53597,53609,53611,53617,53623,
53629,53633,53639,53653,53657,53681,53693,53699,53717,53719,53731,53759,53773,
53777,53783,53791,53813,53819,53831,53849,53857,53861,53881,53887,53891,53897,
53899,53917,53923,53927,53939,53951,53959,53987,53993,54001,54011,54013,54037,
54049,54059,54083,54091,54101,54121,54133,54139,54151,54163,54167,54181,54193,
54217,54251,54269,54277,54287,54293,54311,54319,54323,54331,54347,54361,54367,
54371,54377,54401,54403,54409,54413,54419,54421,54437,54443,54449,54469,54493,
54497,54499,54503,54517,54521,54539,54541,54547,54559,54563,54577,54581,54583,
54601,54617,54623,54629,54631,54647,54667,54673,54679,54709,54713,54721,54727,
54751,54767,54773,54779,54787,54799,54829,54833,54851,54869,54877,54881,54907,
54917,54919,54941,54949,54959,54973,54979,54983,55001,55009,55021,55049,55051,
55057,55061,55073,55079,55103,55109,55117,55127,55147,55163,55171,55201,55207,
55213,55217,55219,55229,55243,55249,55259,55291,55313,55331,55333,55337,55339,
55343,55351,55373,55381,55399,55411,55439,55441,55457,55469,55487,55501,55511,
55529,55541,55547,55579,55589,55603,55609,55619,55621,55631,55633,55639,55661,
55663,55667,55673,55681,55691,55697,55711,55717,55721,55733,55763,55787,55793,
55799,55807,55813,55817,55819,55823,55829,55837,55843,55849,55871,55889,55897,
55901,55903,55921,55927,55931,55933,55949,55967,55987,55997,56003,56009,56039,
56041,56053,56081,56087,56093,56099,56101,56113,56123,56131,56149,56167,56171,
56179,56197,56207,56209,56237,56239,56249,56263,56267,56269,56299,56311,56333,
56359,56369,56377,56383,56393,56401,56417,56431,56437,56443,56453,56467,56473,
56477,56479,56489,56501,56503,56509,56519,56527,56531,56533,56543,56569,56591,
56597,56599,56611,56629,56633,56659,56663,56671,56681,56687,56701,56711,56713,
56731,56737,56747,56767,56773,56779,56783,56807,56809,56813,56821,56827,56843,
56857,56873,56891,56893,56897,56909,56911,56921,56923,56929,56941,56951,56957,
56963,56983,56989,56993,56999,57037,57041,57047,57059,57073,57077,57089,57097,
57107,57119,57131,57139,57143,57149,57163,57173,57179,57191,57193,57203,57221,
57223,57241,57251,57259,57269,57271,57283,57287,57301,57329,57331,57347,57349,
57367,57373,57383,57389,57397,57413,57427,57457,57467,57487,57493,57503,57527,
57529,57557,57559,57571,57587,57593,57601,57637,57641,57649,57653,57667,57679,
57689,57697,57709,57713,57719,57727,57731,57737,57751,57773,57781,57787,57791,
57793,57803,57809,57829,57839,57847,57853,57859,57881,57899,57901,57917,57923,
57943,57947,57973,57977,57991,58013,58027,58031,58043,58049,58057,58061,58067,
58073,58099,58109,58111,58129,58147,58151,58153,58169,58171,58189,58193,58199,
58207,58211,58217,58229,58231,58237,58243,58271,58309,58313,58321,58337,58363,
58367,58369,58379,58391,58393,58403,58411,58417,58427,58439,58441,58451,58453,
58477,58481,58511,58537,58543,58549,58567,58573,58579,58601,58603,58613,58631,
58657,58661,58679,58687,58693,58699,58711,58727,58733,58741,58757,58763,58771,
58787,58789,58831,58889,58897,58901,58907,58909,58913,58921,58937,58943,58963,
58967,58979,58991,58997,59009,59011,59021,59023,59029,59051,59053,59063,59069,
59077,59083,59093,59107,59113,59119,59123,59141,59149,59159,59167,59183,59197,
59207,59209,59219,59221,59233,59239,59243,59263,59273,59281,59333,59341,59351,
59357,59359,59369,59377,59387,59393,59399,59407,59417,59419,59441,59443,59447,
59453,59467,59471,59473,59497,59509,59513,59539,59557,59561,59567,59581,59611,
59617,59621,59627,59629,59651,59659,59663,59669,59671,59693,59699,59707,59723,
59729,59743,59747,59753,59771,59779,59791,59797,59809,59833,59863,59879,59887,
59921,59929,59951,59957,59971,59981,59999,60013,60017,60029,60037,60041,60077,
60083,60089,60091,60101,60103,60107,60127,60133,60139,60149,60161,60167,60169,
60209,60217,60223,60251,60257,60259,60271,60289,60293,60317,60331,60337,60343,
60353,60373,60383,60397,60413,60427,60443,60449,60457,60493,60497,60509,60521,
60527,60539,60589,60601,60607,60611,60617,60623,60631,60637,60647,60649,60659,
60661,60679,60689,60703,60719,60727,60733,60737,60757,60761,60763,60773,60779,
60793,60811,60821,60859,60869,60887,60889,60899,60901,60913,60917,60919,60923,
60937,60943,60953,60961,61001,61007,61027,61031,61043,61051,61057,61091,61099,
61121,61129,61141,61151,61153,61169,61211,61223,61231,61253,61261,61283,61291,
61297,61331,61333,61339,61343,61357,61363,61379,61381,61403,61409,61417,61441,
61463,61469,61471,61483,61487,61493,61507,61511,61519,61543,61547,61553,61559,
61561,61583,61603,61609,61613,61627,61631,61637,61643,61651,61657,61667,61673,
61681,61687,61703,61717,61723,61729,61751,61757,61781,61813,61819,61837,61843,
61861,61871,61879,61909,61927,61933,61949,61961,61967,61979,61981,61987,61991,
62003,62011,62017,62039,62047,62053,62057,62071,62081,62099,62119,62129,62131,
62137,62141,62143,62171,62189,62191,62201,62207,62213,62219,62233,62273,62297,
62299,62303,62311,62323,62327,62347,62351,62383,62401,62417,62423,62459,62467,
62473,62477,62483,62497,62501,62507,62533,62539,62549,62563,62581,62591,62597,
62603,62617,62627,62633,62639,62653,62659,62683,62687,62701,62723,62731,62743,
62753,62761,62773,62791,62801,62819,62827,62851,62861,62869,62873,62897,62903,
62921,62927,62929,62939,62969,62971,62981,62983,62987,62989,63029,63031,63059,
63067,63073,63079,63097,63103,63113,63127,63131,63149,63179,63197,63199,63211,
63241,63247,63277,63281,63299,63311,63313,63317,63331,63337,63347,63353,63361,
63367,63377,63389,63391,63397,63409,63419,63421,63439,63443,63463,63467,63473,
63487,63493,63499,63521,63527,63533,63541,63559,63577,63587,63589,63599,63601,
63607,63611,63617,63629,63647,63649,63659,63667,63671,63689,63691,63697,63703,
63709,63719,63727,63737,63743,63761,63773,63781,63793,63799,63803,63809,63823,
63839,63841,63853,63857,63863,63901,63907,63913,63929,63949,63977,63997,64007,
64013,64019,64033,64037,64063,64067,64081,64091,64109,64123,64151,64153,64157,
64171,64187,64189,64217,64223,64231,64237,64271,64279,64283,64301,64303,64319,
64327,64333,64373,64381,64399,64403,64433,64439,64451,64453,64483,64489,64499,
64513,64553,64567,64577,64579,64591,64601,64609,64613,64621,64627,64633,64661,
64663,64667,64679,64693,64709,64717,64747,64763,64781,64783,64793,64811,64817,
64849,64853,64871,64877,64879,64891,64901,64919,64921,64927,64937,64951,64969,
64997,65003,65011,65027,65029,65033,65053,65063,65071,65089,65099,65101,65111,
65119,65123,65129,65141,65147,65167,65171,65173,65179,65183,65203,65213,65239,
65257,65267,65269,65287,65293,65309,65323,65327,65353,65357,65371,65381,65393,
65407,65413,65419,65423,65437,65447,65449,65479,65497,65519,65521,65537
};
X
/* pr_limit - largest prime in the prime table */
unsigned long *pr_limit = &prime[(sizeof(prime)/sizeof(prime[0]))-1];
SHAR_EOF
chmod 0444 pr_tbl.c ||
echo 'restore of pr_tbl.c failed'
Wc_c="`wc -c < 'pr_tbl.c'`"
test 39958 -eq "$Wc_c" ||
	echo 'pr_tbl.c: original size 39958, current size' "$Wc_c"
fi
# ============= primes.c ==============
if test -f 'primes.c' -a X"$1" != X"-c"; then
	echo 'x - skipping primes.c (File already exists)'
else
echo 'x - extracting primes.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'primes.c' &&
/*
X * Copyright (c) 1989 The Regents of the University of California.
X * All rights reserved.
X *
X * This code is derived from software contributed to Berkeley by
X * Landon Curt Noll.
X *
X * Redistribution and use in source and binary forms are permitted
X * provided that: (1) source distributions retain this entire copyright
X * notice and comment, and (2) distributions including binaries display
X * the following acknowledgement:  ``This product includes software
X * developed by the University of California, Berkeley and its contributors''
X * in the documentation or other materials provided with the distribution
X * and in all advertising materials mentioning features or use of this
X * software. Neither the name of the University nor the names of its
X * contributors may be used to endorse or promote products derived
X * from this software without specific prior written permission.
X * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
X * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
X * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
X */
X
#ifndef lint
char copyright[] =
"@(#) Copyright (c) 1989 The Regents of the University of California.\n\
X All rights reserved.\n";
#endif /* not lint */
X
#ifndef lint
static char sccsid[] = "@(#)primes.c	5.4 (Berkeley) 6/1/90";
#endif /* not lint */
X
/*
X * primes - generate a table of primes between two values
X *
X * By: Landon Curt Noll   chongo@toad.com,   ...!{sun,tolsoft}!hoptoad!chongo
X *
X *   chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
X *
X * usage:
X *	primes [start [stop]]
X *
X *	Print primes >= start and < stop.  If stop is omitted,
X *	the value 4294967295 (2^32-1) is assumed.  If start is
X *	omitted, start is read from standard input.
X *
X *	Prints "ouch" if start or stop is bogus.
X *
X * validation check: there are 664579 primes between 0 and 10^7
X */
X
#include <stdio.h>
#include <math.h>
#include <memory.h>
#include <ctype.h>
#include "primes.h"
X
/*
X * Eratosthenes sieve table
X *
X * We only sieve the odd numbers.  The base of our sieve windows are always
X * odd.  If the base of table is 1, table[i] represents 2*i-1.  After the
X * sieve, table[i] == 1 if and only iff 2*i-1 is prime.
X *
X * We make TABSIZE large to reduce the overhead of inner loop setup.
X */
char table[TABSIZE];	 /* Eratosthenes sieve of odd numbers */
X
/*
X * prime[i] is the (i-1)th prime.
X *
X * We are able to sieve 2^32-1 because this byte table yields all primes 
X * up to 65537 and 65537^2 > 2^32-1.
X */
extern ubig prime[];
extern ubig *pr_limit;		/* largest prime in the prime array */
X
/*
X * To avoid excessive sieves for small factors, we use the table below to 
X * setup our sieve blocks.  Each element represents a odd number starting 
X * with 1.  All non-zero elements are factors of 3, 5, 7, 11 and 13.
X */
extern char pattern[];
extern int pattern_size;	/* length of pattern array */
X
#define MAX_LINE 255    /* max line allowed on stdin */
X
char *read_num_buf();	 /* read a number buffer */
void primes();		 /* print the primes in range */
char *program;		 /* our name */
X
main(argc, argv)
X	int argc;	/* arg count */
X	char *argv[];	/* args */
{
X	char buf[MAX_LINE+1];   /* input buffer */
X	char *ret;	/* return result */
X	ubig start;	/* where to start generating */
X	ubig stop;	/* don't generate at or above this value */
X
X	/*
X	 * parse args
X	 */
X	program = argv[0];
X	start = 0;
X	stop = BIG;
X	if (argc == 3) {
X		/* convert low and high args */
X		if (read_num_buf(NULL, argv[1]) == NULL) {
X			fprintf(stderr, "%s: ouch\n", program);
X			exit(1);
X		}
X		if (read_num_buf(NULL, argv[2]) == NULL) {
X			fprintf(stderr, "%s: ouch\n", program);
X			exit(1);
X		}
X		if (sscanf(argv[1], "%ld", &start) != 1) {
X			fprintf(stderr, "%s: ouch\n", program);
X			exit(1);
X		}
X		if (sscanf(argv[2], "%ld", &stop) != 1) {
X			fprintf(stderr, "%s: ouch\n", program);
X			exit(1);
X		}
X
X	} else if (argc == 2) {
X		/* convert low arg */
X		if (read_num_buf(NULL, argv[1]) == NULL) {
X			fprintf(stderr, "%s: ouch\n", program);
X			exit(1);
X		}
X		if (sscanf(argv[1], "%ld", &start) != 1) {
X			fprintf(stderr, "%s: ouch\n", program);
X			exit(1);
X		}
X
X	} else {
X		/* read input until we get a good line */
X		if (read_num_buf(stdin, buf) != NULL) {
X
X			/* convert the buffer */
X			if (sscanf(buf, "%ld", &start) != 1) {
X				fprintf(stderr, "%s: ouch\n", program);
X				exit(1);
X			}
X		} else {
X			exit(0);
X		}
X	}
X	if (start > stop) {
X		fprintf(stderr, "%s: ouch\n", program);
X		exit(1);
X	}
X	primes(start, stop);
X	exit(0);
}
X
/*
X * read_num_buf - read a number buffer from a stream
X *
X * Read a number on a line of the form:
X *
X *	^[ \t]*\(+?[0-9][0-9]\)*.*$
X *
X * where ? is a 1-or-0 operator and the number is within \( \).
X *
X * If does not match the above pattern, it is ignored and a new
X * line is read.  If the number is too large or small, we will
X * print ouch and read a new line.
X *
X * We have to be very careful on how we check the magnitude of the
X * input.  We can not use numeric checks because of the need to
X * check values against maximum numeric values.
X *
X * This routine will return a line containing a ascii number between
X * 0 and BIG, or it will return NULL.
X *
X * If the stream is NULL then buf will be processed as if were
X * a single line stream.
X *
X * returns:
X *	char *	pointer to leading digit or +
X *	NULL	EOF or error
X */
char *
read_num_buf(input, buf)
X	FILE *input;		/* input stream or NULL */
X	char *buf;		/* input buffer */
{
X	static char limit[MAX_LINE+1];	/* ascii value of BIG */
X	static int limit_len;		/* digit count of limit */
X	int len;			/* digits in input (excluding +/-) */
X	char *s;	/* line start marker */
X	char *d;	/* first digit, skip +/- */
X	char *p;	/* scan pointer */
X	char *z;	/* zero scan pointer */
X
X	/* form the ascii value of SEMIBIG if needed */
X	if (!isascii(limit[0]) || !isdigit(limit[0])) {
X		sprintf(limit, "%ld", SEMIBIG);
X		limit_len = strlen(limit);
X	}
X	
X	/*
X	 * the search for a good line
X	 */
X	if (input != NULL && fgets(buf, MAX_LINE, input) == NULL) {
X		/* error or EOF */
X		return NULL;
X	}
X	do {
X
X		/* ignore leading whitespace */
X		for (s=buf; *s && s < buf+MAX_LINE; ++s) {
X			if (!isascii(*s) || !isspace(*s)) {
X				break;
X			}
X		}
X
X		/* object if - */
X		if (*s == '-') {
X			fprintf(stderr, "%s: ouch\n", program);
X			continue;
X		}
X
X		/* skip over any leading + */
X		if (*s == '+') {
X			d = s+1;
X		} else {
X			d = s;
X		}
X
X		/* note leading zeros */
X		for (z=d; *z && z < buf+MAX_LINE; ++z) {
X			if (*z != '0') {
X				break;
X			}
X		}
X
X		/* scan for the first non-digit/non-plus/non-minus */
X		for (p=d; *p && p < buf+MAX_LINE; ++p) {
X			if (!isascii(*p) || !isdigit(*p)) {
X				break;
X			}
X		}
X
X		/* ignore empty lines */
X		if (p == d) {
X			continue;
X		}
X		*p = '\0';
X
X		/* object if too many digits */
X		len = strlen(z);
X		len = (len<=0) ? 1 : len;
X		/* accept if digit count is below limit */
X		if (len < limit_len) {
X			/* we have good input */
X			return s;
X
X		/* reject very large numbers */
X		} else if (len > limit_len) {
X			fprintf(stderr, "%s: ouch\n", program);
X			continue;
X
X		/* carefully check against near limit numbers */
X		} else if (strcmp(z, limit) > 0) {
X			fprintf(stderr, "%s: ouch\n", program);
X			continue;
X		}
X		/* number is near limit, but is under it */
X		return s;
X	} while (input != NULL && fgets(buf, MAX_LINE, input) != NULL);
X
X	/* error or EOF */
X	return NULL;
}
X
/*
X * primes - sieve and print primes from start up to and but not including stop
X */
void
primes(start, stop)
X	ubig start;	/* where to start generating */
X	ubig stop;	/* don't generate at or above this value */
{
X	register char *q;		/* sieve spot */
X	register ubig factor;		/* index and factor */
X	register char *tab_lim;		/* the limit to sieve on the table */
X	register ubig *p;		/* prime table pointer */
X	register ubig fact_lim;		/* highest prime for current block */
X
X	/*
X	 * A number of systems can not convert double values 
X	 * into unsigned longs when the values are larger than
X	 * the largest signed value.  Thus we take case when
X	 * the double is larger than the value SEMIBIG. *sigh*
X	 */
X	if (start < 3) {
X		start = (ubig)2;
X	}
X	if (stop < 3) {
X		stop = (ubig)2;
X	}
X	if (stop <= start) {
X		return;
X	}
X
X	/*
X	 * be sure that the values are odd, or 2
X	 */
X	if (start != 2 && (start&0x1) == 0) {
X		++start;
X	}
X	if (stop != 2 && (stop&0x1) == 0) {
X		++stop;
X	}
X
X	/*
X	 * quick list of primes <= pr_limit
X	 */
X	if (start <= *pr_limit) {
X		/* skip primes up to the start value */
X		for (p = &prime[0], factor = prime[0];
X		     factor < stop && p <= pr_limit; 
X		     factor = *(++p)) {
X			if (factor >= start) {
X				printf("%u\n", factor);
X			}
X		}
X		/* return early if we are done */
X		if (p <= pr_limit) {
X			return;
X		}
X		start = *pr_limit+2;
X	}
X
X	/*
X	 * we shall sieve a bytemap window, note primes and move the window
X	 * upward until we pass the stop point
X	 */
X	while (start < stop) {
X		/*
X		 * factor out 3, 5, 7, 11 and 13
X		 */
X		/* initial pattern copy */
X		factor = (start%(2*3*5*7*11*13))/2; /* starting copy spot */
X		memcpy(table, &pattern[factor], pattern_size-factor);
X		/* main block pattern copies */
X		for (fact_lim=pattern_size-factor;
X		     fact_lim+pattern_size<=TABSIZE;
X		     fact_lim+=pattern_size) {
X			memcpy(&table[fact_lim], pattern, pattern_size);
X		}
X		/* final block pattern copy */
X		memcpy(&table[fact_lim], pattern, TABSIZE-fact_lim);
X
X		/*
X		 * sieve for primes 17 and higher
X		 */
X		/* note highest useful factor and sieve spot */
X		if (stop-start > TABSIZE+TABSIZE) {
X			tab_lim = &table[TABSIZE]; /* sieve it all */
X			fact_lim = (int)sqrt(
X					(double)(start)+TABSIZE+TABSIZE+1.0);
X		} else {
X			tab_lim = &table[(stop-start)/2]; /* partial sieve */
X			fact_lim = (int)sqrt((double)(stop)+1.0);
X		}
X		/* sieve for factors >= 17 */
X		factor = 17;	/* 17 is first prime to use */
X		p = &prime[7];	/* 19 is next prime, pi(19)=7 */
X		do {
X			/* determine the factor's initial sieve point */
X			q = (char *)(start%factor); /* temp storage for mod */
X			if ((int)q & 0x1) {
X				q = &table[(factor-(int)q)/2];
X			} else {
X				q = &table[q ? factor-((int)q/2) : 0];
X			}
X			/* sive for our current factor */
X			for ( ; q < tab_lim; q += factor) {
X				*q = '\0'; /* sieve out a spot */
X			}
X		} while ((factor=(ubig)(*(p++))) <= fact_lim);
X
X		/*
X		 * print generated primes
X		 */
X		for (q = table; q < tab_lim; ++q, start+=2) {
X			if (*q) {
X				printf("%u\n", start);
X			}
X		}
X	}
}
SHAR_EOF
chmod 0444 primes.c ||
echo 'restore of primes.c failed'
Wc_c="`wc -c < 'primes.c'`"
test 10372 -eq "$Wc_c" ||
	echo 'primes.c: original size 10372, current size' "$Wc_c"
fi
# ============= primes.h ==============
if test -f 'primes.h' -a X"$1" != X"-c"; then
	echo 'x - skipping primes.h (File already exists)'
else
echo 'x - extracting primes.h (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'primes.h' &&
/*
X * Copyright (c) 1989 The Regents of the University of California.
X * All rights reserved.
X *
X * This code is derived from software contributed to Berkeley by
X * Landon Curt Noll.
X *
X * Redistribution and use in source and binary forms are permitted
X * provided that: (1) source distributions retain this entire copyright
X * notice and comment, and (2) distributions including binaries display
X * the following acknowledgement:  ``This product includes software
X * developed by the University of California, Berkeley and its contributors''
X * in the documentation or other materials provided with the distribution
X * and in all advertising materials mentioning features or use of this
X * software. Neither the name of the University nor the names of its
X * contributors may be used to endorse or promote products derived
X * from this software without specific prior written permission.
X * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
X * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
X * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
X *
X *	@(#)primes.h	5.2 (Berkeley) 6/1/90
X */
X
/*
X * primes - generate a table of primes between two values
X *
X * By: Landon Curt Noll   chongo@toad.com,   ...!{sun,tolsoft}!hoptoad!chongo
X *
X *   chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
X */
X
/* ubig is the type that holds a large unsigned value */
typedef unsigned long ubig;           /* must be >=32 bit unsigned value */
X
/*
X * sieve parameters
X */
#define BIG ((ubig)0xffffffff)        /* highest value we will sieve */
#define SEMIBIG ((ubig)0x7fffffff)    /* highest signed value */
#define NEG_SEMIBIG ((ubig)0x80000000) /* lowest signed value */
#define TABSIZE 256*1024 /* bytes in sieve table (must be > 3*5*7*11) */
SHAR_EOF
chmod 0444 primes.h ||
echo 'restore of primes.h failed'
Wc_c="`wc -c < 'primes.h'`"
test 1790 -eq "$Wc_c" ||
	echo 'primes.h: original size 1790, current size' "$Wc_c"
fi
exit 0