$| = 1;

use bigint;

sub min {
	my $min = shift;
	foreach (@_) {
		if ($min > $_) {
			$min = $_;
		}
	}
	return $min;
}

sub max {
	my $max = shift;
	foreach (@_) {
		if ($max < $_) {
			$max = $_;
		}
	}
	return $max;
}

# we deal with sets of intervals
# { 1,2,3 } => [ [1,3] ]
# { 1,  3 } => [ [1,1], [3,3] ]
 
# A, B -> A U B 
sub merge {
	my $a = shift;
	my $b = shift;
	
	my @a = @{$a};
	my @b = @{$b};

	my @ab = ();

	my $ia = 0;
	my $ib = 0;

	while ($ia <= $#a && $ib <= $#b) {
		if ($a[$ia]->[1]+1 < $b[$ib]->[0]) {
			# [a]
			#     [b]
			push @ab => $a[$ia];
			$ia++;
		} elsif ($b[$ib]->[1]+1 < $a[$ia]->[0]) {
			#     [a]
			# [b]
			push @ab => $b[$ib];
			$ib++;
		} else {
			#  [a]
			#   [b]
			my $merged = [ min($a[$ia]->[0], $b[$ib]->[0]),
						   max($a[$ia]->[1], $b[$ib]->[1]) ];
			$ia++;
			$ib++;

			while (1) {
				if ($ia <= $#a && $a[$ia]->[0] <= $merged->[1]+1) {
					$merged = [ $merged->[0], max($merged->[1], $a[$ia]->[1]) ];
					$ia++;
				} elsif ($ib <= $#b && $b[$ib]->[0] <= $merged->[1]+1) {
					$merged = [ $merged->[0], max($merged->[1], $b[$ib]->[1]) ];
					$ib++;
				} else {
					last;
				}
			}

			push @ab => $merged;
		}
	}

	if ($ia <= $#a) {
		push @ab => @a[$ia..$#a];
	} elsif ($ib <= $#b) {
		push @ab => @b[$ib..$#b];
	}

	return \@ab;
}

# A, B -> A \ B
sub remove {
	my $a = shift;
	my $b = shift;
	
	my @a = @{$a};
	my @b = @{$b};

	my @ab = ();

	my $ia = 0;
	my $ib = 0;

	while ($ia <= $#a && $ib <= $#b) {
		if ($a[$ia]->[1] < $b[$ib]->[0]) {
			# [a]
			#     [b]
			push @ab => $a[$ia];
			$ia++;
		} elsif ($b[$ib]->[1] < $a[$ia]->[0]) {
			#     [a]
			# [b]
			$ib++;
		} else {
			#  [a]
			#   [b]

			my $rem = $a[$ia];
			$ia++;

			while (1) {
				if ($ib>$#b) {
					# [rem]
					push @ab => $rem;
					last;
				} elsif ($ib<=$#b && $rem->[0] < $b[$ib]->[0]) {
					# [rem]
					#  [b...
					push @ab => [ $rem->[0], min($rem->[1], $b[$ib]->[0]-1) ];

					if ($rem->[1] > $b[$ib]->[1]) {
						# [rem]
						# ..b]
						$rem = [ $b[$ib]->[1]+1, $rem->[1] ];
						$ib++;
					} else {
						# [rem]
						#  ...b]
						last;
					}
				} else {
					#   [rem]
					# [b..
					if ($rem->[1] > $b[$ib]->[1]) {
						#  [rem]
						#   b]
						$rem = [ $b[$ib]->[1]+1, $rem->[1] ];
						$ib++;
					} else {
						#  rem]
						#     b]
						last;
					}
				}
			}
		}
	}

	if ($ia <= $#a) {
		push @ab => @a[$ia..$#a];
	}

	return \@ab;
}

# A -> A (+) (A+A)
sub move {
	my $set = shift;
	my @set = @{$set};

	my $sum = [];
	foreach my $x (@set) {
		$sum = merge($sum, [ map { [ $x->[0]+$_->[0],
								     $x->[1]+$_->[1] ] } @set ]);
	}

	my $sumMinusSet = remove($sum, $set);
	my $setMinusSum = remove($set, $sum);

	return merge($sumMinusSet,
	             $setMinusSum);
}

sub tostring {
	my $set = shift;
	my @set = @{$set};

	my $string = "";
	my $sep = "";

	foreach (@set) {
		$string .= $sep;
		$sep = ", ";

		my $low = $_->[0];
		my $high = $_->[1];

		if ($low == $high) {
			$string .= "$low";
		} elsif ($low+1 == $high) {
			$string .= "$low,$high";
		} elsif ($low<9 && $low+2 == $high) {
			my $all      = join("," => $low..$high);
			my $ellipsis = "$low...$high";
			if (length($all) <= length($ellipsis)) {
				$string .= $all;
			} else {
				$string .= $ellipsis;
			}
		} else {
			$string .= "$low...$high";
		}
	}

	return "{$string}";
}

sub count {
	my $set = shift;
	my @set = @{$set};
	my $count = 0;
	foreach (@set) {
		$count += $_->[1]-$_->[0]+1;
	}
	return $count;
}

my $set = [ [1,1] ];
my $max = 250;
foreach my $n (1..$max) {
	print $n, " ", count($set), "\n";
	if ($n < $max) {
		$set = move($set);
	}
}