#include <stdio.h>

void hanoi (int n, char *a, char *b, char *c);

unsigned long calls;
unsigned long quints;

main () 
{
	int x;
	extern unsigned long calls;
	extern unsigned long quints;

	printf("Towers of Hanoi\n");

	printf("Enter the number of disks to move (0 to quit):\n");
	scanf("%d", &x);

	printf("The following number of calls is required for %d disks:\n", x);

	while (x > 0)
	{
		calls = 0;
		quints = 0;

		hanoi (x, "A", "B", "C");	/* x disks */
		
		printf("Call number: %21d%018d\n", quints, calls);

		printf("Enter the number of disks to move (0 to quit):\n");
		scanf("%d", &x);
	}
}

void hanoi (int n, char *a, char *b, char *c)
{
	extern unsigned long calls;
	extern unsigned long quints;

	if (n == 1)
	{
		if ((++calls) == 1000000000000000000)
		{
			quints++;
			printf("Call number: %21d%018d\n", quints, 0);
			calls = 0;
		}
		return;
	}

	hanoi (n-1, a, c, b);
	if ((++calls) == 1000000000000000000)
	{
		quints++;
		printf("Call number: %21d%018d\n", quints, 0);
		calls = 0;
	}
	hanoi (n-1, b, a, c);
}