Given the following C code and unoptimized assembly code, your task is to generate highly optimized x86-64 assembly code.
C Code:

```c
#include <stdio.h>
#include <string.h>
#include <inttypes.h>

/*
答えはXに依存しないと予想できる -> はずれ

N=2 len=3
N=3 len=6
N=4 len=9 (X=2 -> len=6)
N=5 len=12

*/

#define KABE_MIGI 1
#define KABE_UE 2
#define KABE_SITA 4

char kabe[2000][2000];

uint64_t solve(uint64_t N, uint64_t X) {
	memset(kabe, 0, sizeof(kabe));
	if (N <= 1000) {
		static const uint64_t dputtern[6][2] = {
			{0, 1}, /* 右 */
			{-1, 0}, /* 右上 */
			{1, 1}, /* 右下 */
			{0, -1}, /* 左 */
			{-1, -1}, /* 左上 */
			{1, 0} /* 左下 */
		};
		uint64_t i;
		uint64_t y, x;
		int d;
		int invalid;
		uint64_t answer = 0;
		for (i = 1; i <= N; i++) {
			kabe[10+i][10+0] = KABE_UE; /* 左 */
			kabe[10+i - 1][10+i - 1] = KABE_SITA; /* 右 */
			kabe[10+N][10+i - 1] = KABE_MIGI; /* 底辺 */
		}
		y = 10+X;
		x = 10;
		d = 0; /* 右 */
		while (answer == 0 || y != 10+X || x != 10) {
			/* 壁を生やして移動する */
			switch(d) {
				case 0: kabe[y][x] |= KABE_MIGI; break;
				case 1: kabe[y][x] |= KABE_UE; break;
				case 2: kabe[y][x] |= KABE_SITA; break;
				case 3: kabe[y][x-1] |= KABE_MIGI; break;
				case 4: kabe[y-1][x-1] |= KABE_SITA; break;
				case 5: kabe[y+1][x] |= KABE_UE; break;
			}
			y += dputtern[d][0];
			x += dputtern[d][1];
			answer++;
#if 0
			printf("%d %d %d %d\n", (int)(x-10),(int)(y-10),d, kabe[y][x]);fflush(stdout);
			if(answer>20)break;
#endif
			/* 反射する */
			invalid = 1;
			if ((kabe[y][x] & KABE_MIGI) || (kabe[y][x-1] & KABE_MIGI)) {
				invalid = 0;
				switch(d) {
					case 0: invalid = 1; break;
					case 1: d = 2; break;
					case 2: d = 1; break;
					case 3: invalid = 1; break;
					case 4: d = 5; break;
					case 5: d = 4; break;
				}
			}
			if (invalid && ((kabe[y][x] & KABE_UE) || (kabe[y+1][x] & KABE_UE))) {
				invalid = 0;
				switch(d) {
					case 0: d = 4; break;
					case 1: invalid = 1; break;
					case 2: d = 3; break;
					case 3: d = 2; break;
					case 4: d = 0; break;
					case 5: invalid = 1; break;
				}
			}
			if (invalid && ((kabe[y][x] & KABE_SITA) || (kabe[y-1][x-1] & KABE_SITA))) {
				switch(d) {
					case 0: d = 5; break;
					case 1: d = 3; break;
					case 2: invalid = 1; break;
					case 3: d = 1; break;
					case 4: invalid = 1; break;
					case 5: d = 0; break;
				}
			}
		}
		return answer;
	} else {
		/* not implemented */
		return  UINT64_C(3) * (N - 1);
	}
}

uint64_t gcd(uint64_t a, uint64_t b) {
	uint64_t r;
	while (b) {
		r = a % b;
		a = b;
		b = r;
	}
	return a;
}

int main(void) {
	uint64_t N, X;
#if 0
	int wacount = 0;
	for (N = 2; N < 200; N++) {
		for (X = 1; X < N; X++) {
			uint64_t a = solve(N, X);
			uint64_t p = UINT64_C(3) * (N - gcd(N, X));
			if (a != p) {
				printf("Wrong answer N = %"PRIu64", X = %"PRIu64", a = %"PRIu64", p = %"PRIu64"\n", N, X, a, p);
				if (++wacount >= 10) return 0;
			}
		}
	}
#else
	if (scanf("%"SCNu64"%"SCNu64, &N, &X) != 2) return 1;
#if 0
	printf("%"PRIu64"\n", solve(N, X));
#else
	printf("%"PRIu64"\n", UINT64_C(3) * (N - gcd(N, X)));
#endif
#endif
	return 0;
}
```

Unoptimized Assembly Code:

```assembly
	.file	"temp.c"
	.text
	.globl	kabe
	.bss
	.align 32
	.type	kabe, @object
	.size	kabe, 4000000
kabe:
	.zero	4000000
	.text
	.globl	solve
	.type	solve, @function
solve:
.LFB0:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$64, %rsp
	movq	%rdi, -56(%rbp)
	movq	%rsi, -64(%rbp)
	movl	$4000000, %edx
	movl	$0, %esi
	leaq	kabe(%rip), %rax
	movq	%rax, %rdi
	call	memset@PLT
	cmpq	$1000, -56(%rbp)
	ja	.L2
	movq	$0, -8(%rbp)
	movq	$1, -32(%rbp)
	jmp	.L3
.L4:
	movq	-32(%rbp), %rax
	addq	$10, %rax
	imulq	$2000, %rax, %rax
	leaq	10+kabe(%rip), %rdx
	movb	$2, (%rax,%rdx)
	movq	-32(%rbp), %rax
	leaq	9(%rax), %rdx
	movq	-32(%rbp), %rax
	leaq	9(%rax), %rcx
	imulq	$2000, %rdx, %rax
	leaq	(%rax,%rcx), %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movb	$4, (%rax)
	movq	-56(%rbp), %rax
	leaq	10(%rax), %rdx
	movq	-32(%rbp), %rax
	leaq	9(%rax), %rcx
	imulq	$2000, %rdx, %rax
	leaq	(%rax,%rcx), %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movb	$1, (%rax)
	addq	$1, -32(%rbp)
.L3:
	movq	-32(%rbp), %rax
	cmpq	-56(%rbp), %rax
	jbe	.L4
	movq	-64(%rbp), %rax
	addq	$10, %rax
	movq	%rax, -24(%rbp)
	movq	$10, -16(%rbp)
	movl	$0, -40(%rbp)
	nop
	jmp	.L32
.L41:
	cmpl	$5, -40(%rbp)
	ja	.L6
	movl	-40(%rbp), %eax
	leaq	0(,%rax,4), %rdx
	leaq	.L8(%rip), %rax
	movl	(%rdx,%rax), %eax
	cltq
	leaq	.L8(%rip), %rdx
	addq	%rdx, %rax
	notrack jmp	*%rax
	.section	.rodata
	.align 4
	.align 4
.L8:
	.long	.L13-.L8
	.long	.L12-.L8
	.long	.L11-.L8
	.long	.L10-.L8
	.long	.L9-.L8
	.long	.L7-.L8
	.text
.L13:
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	orl	$1, %eax
	movl	%eax, %edx
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rcx
	movq	-16(%rbp), %rax
	addq	%rax, %rcx
	leaq	kabe(%rip), %rax
	addq	%rcx, %rax
	movb	%dl, (%rax)
	jmp	.L6
.L12:
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	orl	$2, %eax
	movl	%eax, %edx
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rcx
	movq	-16(%rbp), %rax
	addq	%rax, %rcx
	leaq	kabe(%rip), %rax
	addq	%rcx, %rax
	movb	%dl, (%rax)
	jmp	.L6
.L11:
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	orl	$4, %eax
	movl	%eax, %edx
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rcx
	movq	-16(%rbp), %rax
	addq	%rax, %rcx
	leaq	kabe(%rip), %rax
	addq	%rcx, %rax
	movb	%dl, (%rax)
	jmp	.L6
.L10:
	movq	-16(%rbp), %rax
	leaq	-1(%rax), %rdx
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movq	-16(%rbp), %rdx
	leaq	-1(%rdx), %rcx
	orl	$1, %eax
	movl	%eax, %edx
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rax
	addq	%rax, %rcx
	leaq	kabe(%rip), %rax
	addq	%rcx, %rax
	movb	%dl, (%rax)
	jmp	.L6
.L9:
	movq	-24(%rbp), %rax
	leaq	-1(%rax), %rdx
	movq	-16(%rbp), %rax
	leaq	-1(%rax), %rcx
	imulq	$2000, %rdx, %rax
	leaq	(%rax,%rcx), %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movq	-24(%rbp), %rdx
	leaq	-1(%rdx), %rcx
	movq	-16(%rbp), %rdx
	leaq	-1(%rdx), %rsi
	orl	$4, %eax
	movl	%eax, %edx
	imulq	$2000, %rcx, %rax
	leaq	(%rax,%rsi), %rcx
	leaq	kabe(%rip), %rax
	addq	%rcx, %rax
	movb	%dl, (%rax)
	jmp	.L6
.L7:
	movq	-24(%rbp), %rax
	addq	$1, %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movq	-24(%rbp), %rdx
	leaq	1(%rdx), %rcx
	orl	$2, %eax
	movl	%eax, %edx
	imulq	$2000, %rcx, %rcx
	movq	-16(%rbp), %rax
	addq	%rax, %rcx
	leaq	kabe(%rip), %rax
	addq	%rcx, %rax
	movb	%dl, (%rax)
	nop
.L6:
	movl	-40(%rbp), %eax
	cltq
	salq	$4, %rax
	movq	%rax, %rdx
	leaq	dputtern.0(%rip), %rax
	movq	(%rdx,%rax), %rax
	addq	%rax, -24(%rbp)
	movl	-40(%rbp), %eax
	cltq
	salq	$4, %rax
	movq	%rax, %rdx
	leaq	8+dputtern.0(%rip), %rax
	movq	(%rdx,%rax), %rax
	addq	%rax, -16(%rbp)
	addq	$1, -8(%rbp)
	movl	$1, -36(%rbp)
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movsbl	%al, %eax
	andl	$1, %eax
	testl	%eax, %eax
	jne	.L14
	movq	-16(%rbp), %rax
	leaq	-1(%rax), %rdx
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movsbl	%al, %eax
	andl	$1, %eax
	testl	%eax, %eax
	je	.L15
.L14:
	movl	$0, -36(%rbp)
	cmpl	$5, -40(%rbp)
	ja	.L15
	movl	-40(%rbp), %eax
	leaq	0(,%rax,4), %rdx
	leaq	.L17(%rip), %rax
	movl	(%rdx,%rax), %eax
	cltq
	leaq	.L17(%rip), %rdx
	addq	%rdx, %rax
	notrack jmp	*%rax
	.section	.rodata
	.align 4
	.align 4
.L17:
	.long	.L22-.L17
	.long	.L21-.L17
	.long	.L20-.L17
	.long	.L19-.L17
	.long	.L18-.L17
	.long	.L16-.L17
	.text
.L22:
	movl	$1, -36(%rbp)
	jmp	.L15
.L21:
	movl	$2, -40(%rbp)
	jmp	.L15
.L20:
	movl	$1, -40(%rbp)
	jmp	.L15
.L19:
	movl	$1, -36(%rbp)
	jmp	.L15
.L18:
	movl	$5, -40(%rbp)
	jmp	.L15
.L16:
	movl	$4, -40(%rbp)
	nop
.L15:
	cmpl	$0, -36(%rbp)
	je	.L23
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movsbl	%al, %eax
	andl	$2, %eax
	testl	%eax, %eax
	jne	.L24
	movq	-24(%rbp), %rax
	addq	$1, %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movsbl	%al, %eax
	andl	$2, %eax
	testl	%eax, %eax
	je	.L23
.L24:
	movl	$0, -36(%rbp)
	cmpl	$5, -40(%rbp)
	ja	.L23
	movl	-40(%rbp), %eax
	leaq	0(,%rax,4), %rdx
	leaq	.L26(%rip), %rax
	movl	(%rdx,%rax), %eax
	cltq
	leaq	.L26(%rip), %rdx
	addq	%rdx, %rax
	notrack jmp	*%rax
	.section	.rodata
	.align 4
	.align 4
.L26:
	.long	.L31-.L26
	.long	.L30-.L26
	.long	.L29-.L26
	.long	.L28-.L26
	.long	.L27-.L26
	.long	.L25-.L26
	.text
.L31:
	movl	$4, -40(%rbp)
	jmp	.L23
.L30:
	movl	$1, -36(%rbp)
	jmp	.L23
.L29:
	movl	$3, -40(%rbp)
	jmp	.L23
.L28:
	movl	$2, -40(%rbp)
	jmp	.L23
.L27:
	movl	$0, -40(%rbp)
	jmp	.L23
.L25:
	movl	$1, -36(%rbp)
	nop
.L23:
	cmpl	$0, -36(%rbp)
	je	.L32
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movsbl	%al, %eax
	andl	$4, %eax
	testl	%eax, %eax
	jne	.L33
	movq	-24(%rbp), %rax
	leaq	-1(%rax), %rdx
	movq	-16(%rbp), %rax
	leaq	-1(%rax), %rcx
	imulq	$2000, %rdx, %rax
	leaq	(%rax,%rcx), %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movsbl	%al, %eax
	andl	$4, %eax
	testl	%eax, %eax
	je	.L32
.L33:
	cmpl	$5, -40(%rbp)
	ja	.L32
	movl	-40(%rbp), %eax
	leaq	0(,%rax,4), %rdx
	leaq	.L35(%rip), %rax
	movl	(%rdx,%rax), %eax
	cltq
	leaq	.L35(%rip), %rdx
	addq	%rdx, %rax
	notrack jmp	*%rax
	.section	.rodata
	.align 4
	.align 4
.L35:
	.long	.L40-.L35
	.long	.L39-.L35
	.long	.L38-.L35
	.long	.L37-.L35
	.long	.L36-.L35
	.long	.L34-.L35
	.text
.L40:
	movl	$5, -40(%rbp)
	jmp	.L32
.L39:
	movl	$3, -40(%rbp)
	jmp	.L32
.L38:
	movl	$1, -36(%rbp)
	jmp	.L32
.L37:
	movl	$1, -40(%rbp)
	jmp	.L32
.L36:
	movl	$1, -36(%rbp)
	jmp	.L32
.L34:
	movl	$0, -40(%rbp)
	nop
.L32:
	cmpq	$0, -8(%rbp)
	je	.L41
	movq	-64(%rbp), %rax
	addq	$10, %rax
	cmpq	%rax, -24(%rbp)
	jne	.L41
	cmpq	$10, -16(%rbp)
	jne	.L41
	movq	-8(%rbp), %rax
	jmp	.L42
.L2:
	movq	-56(%rbp), %rdx
	movq	%rdx, %rax
	addq	%rax, %rax
	addq	%rdx, %rax
	subq	$3, %rax
.L42:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE0:
	.size	solve, .-solve
	.globl	gcd
	.type	gcd, @function
gcd:
.LFB1:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movq	%rdi, -24(%rbp)
	movq	%rsi, -32(%rbp)
	jmp	.L44
.L45:
	movq	-24(%rbp), %rax
	movl	$0, %edx
	divq	-32(%rbp)
	movq	%rdx, -8(%rbp)
	movq	-32(%rbp), %rax
	movq	%rax, -24(%rbp)
	movq	-8(%rbp), %rax
	movq	%rax, -32(%rbp)
.L44:
	cmpq	$0, -32(%rbp)
	jne	.L45
	movq	-24(%rbp), %rax
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE1:
	.size	gcd, .-gcd
	.section	.rodata
.LC0:
	.string	"%lu%lu"
.LC1:
	.string	"%lu\n"
	.text
	.globl	main
	.type	main, @function
main:
.LFB2:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	pushq	%rbx
	subq	$40, %rsp
	.cfi_offset 3, -24
	movq	%fs:40, %rax
	movq	%rax, -24(%rbp)
	xorl	%eax, %eax
	leaq	-32(%rbp), %rdx
	leaq	-40(%rbp), %rax
	movq	%rax, %rsi
	leaq	.LC0(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	cmpl	$2, %eax
	je	.L48
	movl	$1, %eax
	jmp	.L50
.L48:
	movq	-40(%rbp), %rbx
	movq	-32(%rbp), %rdx
	movq	-40(%rbp), %rax
	movq	%rdx, %rsi
	movq	%rax, %rdi
	call	gcd
	subq	%rax, %rbx
	movq	%rbx, %rdx
	movq	%rdx, %rax
	addq	%rax, %rax
	addq	%rdx, %rax
	movq	%rax, %rsi
	leaq	.LC1(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
	movl	$0, %eax
.L50:
	movq	-24(%rbp), %rdx
	subq	%fs:40, %rdx
	je	.L51
	call	__stack_chk_fail@PLT
.L51:
	movq	-8(%rbp), %rbx
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE2:
	.size	main, .-main
	.section	.rodata
	.align 32
	.type	dputtern.0, @object
	.size	dputtern.0, 96
dputtern.0:
	.quad	0
	.quad	1
	.quad	-1
	.quad	0
	.quad	1
	.quad	1
	.quad	0
	.quad	-1
	.quad	-1
	.quad	-1
	.quad	1
	.quad	0
	.ident	"GCC: (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:
```

Only output the optimized assembly code. Do not include any other text. Do not write any comments in the assembly code. Wrap the assembly code in ```assembly``` tags.
user
	.file	"temp.c"
	.text
	.p2align 4
	.globl	solve
	.type	solve, @function
solve:
.LFB35:
	.cfi_startproc
	endbr64
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	leaq	kabe(%rip), %r9
	movl	$4000000, %edx
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	pushq	%r13
	.cfi_def_cfa_offset 32
	.cfi_offset 13, -32
	pushq	%r12
	.cfi_def_cfa_offset 40
	.cfi_offset 12, -40
	movq	%rsi, %r12
	xorl	%esi, %esi
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	movq	%rdi, %rbx
	movq	%r9, %rdi
	subq	$8, %rsp
	.cfi_def_cfa_offset 64
	call	memset@PLT
	cmpq	$1000, %rbx
	ja	.L2
	movq	%rax, %r9
	testq	%rbx, %rbx
	je	.L8
	imulq	$2001, %rbx, %rsi
	leaq	10(%rbx), %rdi
	imulq	$2000, %rbx, %r10
	leaq	20010(%rax,%rsi), %rbp
	leaq	20010+kabe(%rip), %rax
	addq	$18010, %rsi
	leaq	20010(%r10), %rcx
	cmpq	%rax, %rbp
	leaq	20011(%r10), %r11
	setbe	%r8b
	cmpq	%rcx, %rsi
	setle	%dl
	orl	%edx, %r8d
	leaq	2000(%rax), %rdx
	cmpq	%rdx, %rbp
	setbe	%bpl
	cmpq	%r11, %rcx
	setge	%r13b
	orl	%r13d, %ebp
	andl	%ebp, %r8d
	leaq	-1(%rbx), %rbp
	cmpq	$21, %rbp
	seta	%bpl
	testb	%bpl, %r8b
	je	.L5
	addq	%r9, %rsi
	cmpq	%rdx, %rsi
	leaq	(%r9,%r11), %rsi
	setbe	%r8b
	cmpq	%rax, %rsi
	setbe	%sil
	orb	%sil, %r8b
	je	.L5
	movq	%rbx, %rsi
	addq	%r9, %rcx
	movdqa	.LC0(%rip), %xmm0
	andq	$-16, %rsi
	addq	%rcx, %rsi
	.p2align 4,,10
	.p2align 3
.L6:
	movb	$2, (%rdx)
	addq	$16, %rcx
	addq	$32016, %rax
	addq	$32000, %rdx
	movb	$2, -30000(%rdx)
	movb	$2, -28000(%rdx)
	movb	$2, -26000(%rdx)
	movb	$2, -24000(%rdx)
	movb	$2, -22000(%rdx)
	movb	$2, -20000(%rdx)
	movb	$2, -18000(%rdx)
	movb	$2, -16000(%rdx)
	movb	$2, -14000(%rdx)
	movb	$2, -12000(%rdx)
	movb	$2, -10000(%rdx)
	movb	$2, -8000(%rdx)
	movb	$2, -6000(%rdx)
	movb	$2, -4000(%rdx)
	movb	$2, -2000(%rdx)
	movb	$4, -32016(%rax)
	movb	$4, -30015(%rax)
	movb	$4, -28014(%rax)
	movb	$4, -26013(%rax)
	movb	$4, -24012(%rax)
	movb	$4, -22011(%rax)
	movb	$4, -20010(%rax)
	movb	$4, -18009(%rax)
	movb	$4, -16008(%rax)
	movb	$4, -14007(%rax)
	movb	$4, -12006(%rax)
	movb	$4, -10005(%rax)
	movb	$4, -8004(%rax)
	movb	$4, -6003(%rax)
	movb	$4, -4002(%rax)
	movb	$4, -2001(%rax)
	movups	%xmm0, -16(%rcx)
	cmpq	%rsi, %rcx
	jne	.L6
	movq	%rbx, %rax
	andq	$-16, %rax
	testb	$15, %bl
	je	.L8
	leaq	11(%rax), %rsi
	leaq	10(%rax), %r10
	imulq	$2000, %rsi, %rdx
	leaq	2(%rax), %rcx
	movb	$2, 10(%r9,%rdx)
	imulq	$2001, %r10, %rdx
	movb	$4, (%r9,%rdx)
	imulq	$2000, %rdi, %rdx
	addq	%r9, %rdx
	movb	$1, 10(%rax,%rdx)
	cmpq	%rcx, %rbx
	jb	.L8
	leaq	12(%rax), %r8
	imulq	$2000, %r8, %rcx
	movb	$2, 10(%r9,%rcx)
	imulq	$2001, %rsi, %rcx
	movb	$4, (%r9,%rcx)
	leaq	3(%rax), %rcx
	movb	$1, 11(%rax,%rdx)
	cmpq	%rcx, %rbx
	jb	.L8
	leaq	13(%rax), %r11
	imulq	$2000, %r11, %rcx
	movb	$2, 10(%r9,%rcx)
	imulq	$2001, %r8, %rcx
	movb	$4, (%r9,%rcx)
	leaq	4(%rax), %rcx
	movb	$1, 12(%rax,%rdx)
	cmpq	%rcx, %rbx
	jb	.L8
	leaq	14(%rax), %rbp
	imulq	$2000, %rbp, %rcx
	movb	$2, 10(%r9,%rcx)
	imulq	$2001, %r11, %rcx
	movb	$4, (%r9,%rcx)
	leaq	5(%rax), %rcx
	movb	$1, 13(%rax,%rdx)
	cmpq	%rcx, %rbx
	jb	.L8
	leaq	15(%rax), %r13
	imulq	$2000, %r13, %rcx
	movb	$2, 10(%r9,%rcx)
	imulq	$2001, %rbp, %rcx
	movb	$4, (%r9,%rcx)
	leaq	6(%rax), %rcx
	movb	$1, 14(%rax,%rdx)
	cmpq	%rcx, %rbx
	jb	.L8
	leaq	16(%rax), %rcx
	imulq	$2000, %rcx, %r14
	movb	$2, 10(%r9,%r14)
	imulq	$2001, %r13, %r14
	movb	$4, (%r9,%r14)
	leaq	7(%rax), %r14
	movb	$1, 15(%rax,%rdx)
	cmpq	%r14, %rbx
	jb	.L8
	leaq	17(%rax), %r14
	imulq	$2000, %r14, %r15
	movb	$2, 10(%r9,%r15)
	imulq	$2001, %rcx, %r15
	leaq	8(%rax), %rcx
	movb	$4, (%r9,%r15)
	movb	$1, 16(%rax,%rdx)
	cmpq	%rcx, %rbx
	jb	.L8
	leaq	18(%rax), %rcx
	imulq	$2000, %rcx, %r15
	movb	$2, 10(%r9,%r15)
	imulq	$2001, %r14, %r15
	movb	$4, (%r9,%r15)
	movb	$1, 17(%rax,%rdx)
	leaq	9(%rax), %rdx
	cmpq	%rdx, %rbx
	jb	.L8
	leaq	19(%rax), %r14
	imulq	$2000, %r14, %rdx
	movb	$2, 10(%r9,%rdx)
	imulq	$2001, %rcx, %rdx
	movb	$4, (%r9,%rdx)
	imulq	$2000, %rdi, %rdx
	addq	%r9, %rdx
	movb	$1, 18(%rax,%rdx)
	cmpq	%r10, %rbx
	jb	.L8
	leaq	20(%rax), %rcx
	imulq	$2000, %rcx, %rdi
	movb	$2, 10(%r9,%rdi)
	imulq	$2001, %r14, %rdi
	movb	$4, (%r9,%rdi)
	movb	$1, 19(%rax,%rdx)
	cmpq	%rsi, %rbx
	jb	.L8
	leaq	21(%rax), %rsi
	imulq	$2000, %rsi, %rdi
	movb	$2, 10(%r9,%rdi)
	imulq	$2001, %rcx, %rdi
	movb	$4, (%r9,%rdi)
	movb	$1, 20(%rax,%rdx)
	cmpq	%r8, %rbx
	jb	.L8
	leaq	22(%rax), %rcx
	imulq	$2000, %rcx, %rdi
	movb	$2, 10(%r9,%rdi)
	imulq	$2001, %rsi, %rdi
	movb	$4, (%r9,%rdi)
	movb	$1, 21(%rax,%rdx)
	cmpq	%r11, %rbx
	jb	.L8
	leaq	23(%rax), %rsi
	imulq	$2000, %rsi, %rdi
	movb	$2, 10(%r9,%rdi)
	imulq	$2001, %rcx, %rdi
	movb	$4, (%r9,%rdi)
	movb	$1, 22(%rax,%rdx)
	cmpq	%rbp, %rbx
	jb	.L8
	leaq	24(%rax), %rcx
	imulq	$2000, %rcx, %rdi
	movb	$2, 10(%r9,%rdi)
	imulq	$2001, %rsi, %rdi
	movb	$4, (%r9,%rdi)
	movb	$1, 23(%rax,%rdx)
	cmpq	%r13, %rbx
	jb	.L8
	addq	$25, %rax
	imulq	$2000, %rax, %rax
	movb	$2, 10(%r9,%rax)
	imulq	$2001, %rcx, %rax
	movb	$4, (%r9,%rax)
	movb	$1, (%rdx,%rcx)
	.p2align 4,,10
	.p2align 3
.L8:
	addq	$10, %r12
	movl	$1, %ebx
	xorl	%ebp, %ebp
	xorl	%r8d, %r8d
	movq	%r12, %rsi
	xorl	%eax, %eax
	movl	$10, %ecx
	leaq	.L14(%rip), %r14
	leaq	.L29(%rip), %r13
	.p2align 4,,10
	.p2align 3
.L60:
	cmpl	$5, %eax
	ja	.L12
	movslq	(%r14,%rax,4), %rax
	addq	%r14, %rax
	notrack jmp	*%rax
	.section	.rodata
	.align 4
	.align 4
.L14:
	.long	.L12-.L14
	.long	.L18-.L14
	.long	.L17-.L14
	.long	.L16-.L14
	.long	.L15-.L14
	.long	.L13-.L14
	.text
	.p2align 4,,10
	.p2align 3
.L23:
	testb	%dil, %dil
	je	.L1
.L15:
	subq	$1, %rsi
	subq	$1, %rcx
	movq	$-1, %rbx
	movq	$-1, %rbp
	imulq	$2000, %rsi, %rax
	addq	%r9, %rax
	addq	%rcx, %rax
	movzbl	(%rax), %edx
	orl	$4, %edx
	cmpq	$10, %rcx
	setne	%r11b
	cmpq	%r12, %rsi
	movb	%dl, (%rax)
	movl	$4, %eax
	setne	%r10b
.L19:
	addq	$1, %r8
	testb	$1, %dl
	jne	.L20
.L68:
	imulq	$2000, %rsi, %rdi
	addq	%r9, %rdi
	testb	$1, -1(%rcx,%rdi)
	jne	.L20
.L21:
	testb	$2, %dl
	jne	.L26
	leaq	1(%rsi), %rdi
	imulq	$2000, %rdi, %rdi
	addq	%r9, %rdi
	testb	$2, (%rdi,%rcx)
	je	.L27
.L26:
	testq	%r8, %r8
	movl	%r11d, %edi
	sete	%r15b
	orl	%r10d, %edi
	orl	%edi, %r15d
	cmpl	$5, %eax
	ja	.L28
	movl	%eax, %edi
	movslq	0(%r13,%rdi,4), %rdi
	addq	%r13, %rdi
	notrack jmp	*%rdi
	.section	.rodata
	.align 4
	.align 4
.L29:
	.long	.L28-.L29
	.long	.L27-.L29
	.long	.L32-.L29
	.long	.L31-.L29
	.long	.L30-.L29
	.long	.L27-.L29
	.text
	.p2align 4,,10
	.p2align 3
.L27:
	testb	$4, %dl
	jne	.L35
	leaq	-1(%rsi), %rdi
	imulq	$2000, %rdi, %rdi
	addq	%r9, %rdi
	testb	$4, -1(%rcx,%rdi)
	jne	.L35
.L36:
	testq	%r8, %r8
	je	.L60
	orb	%r11b, %r10b
	jne	.L60
.L1:
	addq	$8, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 56
	movq	%r8, %rax
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%rbp
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r13
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	ret
	.p2align 4,,10
	.p2align 3
.L30:
	.cfi_restore_state
	xorl	%ebp, %ebp
	movl	$1, %ebx
	testb	%r15b, %r15b
	je	.L1
.L47:
	movq	%rsi, %rax
.L43:
	imulq	$2000, %rax, %rax
	orl	$1, %edx
	addq	%r9, %rax
	movb	%dl, (%rax,%rcx)
	imulq	$2000, %rsi, %rax
	addq	%rbx, %rcx
	addq	%r9, %rax
	cmpq	$10, %rcx
	movzbl	(%rax,%rcx), %edx
	setne	%r11b
	xorl	%eax, %eax
	addq	$1, %r8
	testb	$1, %dl
	je	.L68
	.p2align 4,,10
	.p2align 3
.L20:
	testq	%r8, %r8
	movl	%r11d, %r15d
	sete	%dil
	orl	%r10d, %r15d
	orl	%r15d, %edi
	cmpl	$4, %eax
	je	.L39
	cmpl	$5, %eax
	je	.L23
	cmpl	$1, %eax
	je	.L24
	cmpl	$2, %eax
	jne	.L21
.L25:
	testb	%dil, %dil
	je	.L1
.L44:
	imulq	$2000, %rsi, %rax
	orl	$2, %edx
	subq	$1, %rsi
	movq	$-1, %rbp
	addq	%r9, %rax
	movb	%dl, (%rax,%rcx)
	imulq	$2000, %rsi, %rax
	addq	%r9, %rax
	cmpq	%rsi, %r12
	movzbl	(%rax,%rcx), %edx
	setne	%r10b
	movl	$1, %eax
	xorl	%ebx, %ebx
	jmp	.L19
	.p2align 4,,10
	.p2align 3
.L31:
	testb	%r15b, %r15b
	je	.L1
.L45:
	imulq	$2000, %rsi, %rax
	orl	$4, %edx
	addq	$1, %rsi
	movl	$1, %ebx
	movl	$1, %ebp
	addq	%r9, %rax
	movb	%dl, (%rax,%rcx)
	imulq	$2000, %rsi, %rax
	addq	$1, %rcx
	addq	%r9, %rax
	cmpq	$10, %rcx
	setne	%r11b
	cmpq	%rsi, %r12
	movzbl	(%rax,%rcx), %edx
	movl	$2, %eax
	setne	%r10b
	jmp	.L19
	.p2align 4,,10
	.p2align 3
.L32:
	testb	%r15b, %r15b
	je	.L1
.L42:
	imulq	$2000, %rsi, %rax
	subq	$1, %rcx
	movq	$-1, %rbx
	addq	%r9, %rax
	addq	%rcx, %rax
	movzbl	(%rax), %edx
	orl	$1, %edx
	cmpq	$10, %rcx
	movb	%dl, (%rax)
	setne	%r11b
	movl	$3, %eax
	xorl	%ebp, %ebp
	jmp	.L19
	.p2align 4,,10
	.p2align 3
.L35:
	testq	%r8, %r8
	movl	%r11d, %r15d
	sete	%dil
	orl	%r10d, %r15d
	orl	%r15d, %edi
	cmpl	$3, %eax
	je	.L25
	jg	.L38
	testl	%eax, %eax
	je	.L39
	cmpl	$1, %eax
	jne	.L36
	testb	%dil, %dil
	jne	.L42
	jmp	.L1
	.p2align 4,,10
	.p2align 3
.L38:
	cmpl	$5, %eax
	jne	.L36
	xorl	%ebp, %ebp
	movl	$1, %ebx
	testb	%dil, %dil
	jne	.L47
	jmp	.L1
	.p2align 4,,10
	.p2align 3
.L39:
	testb	%dil, %dil
	je	.L1
.L33:
	addq	$1, %rsi
	movl	$1, %ebp
	imulq	$2000, %rsi, %rax
	addq	%r9, %rax
	addq	%rcx, %rax
	movzbl	(%rax), %edx
	orl	$2, %edx
	cmpq	%r12, %rsi
	movb	%dl, (%rax)
	setne	%r10b
	movl	$5, %eax
	xorl	%ebx, %ebx
	jmp	.L19
	.p2align 4,,10
	.p2align 3
.L24:
	testb	%dil, %dil
	jne	.L45
	jmp	.L1
	.p2align 4,,10
	.p2align 3
.L28:
	testb	%r15b, %r15b
	jne	.L15
	jmp	.L1
	.p2align 4,,10
	.p2align 3
.L2:
	leaq	-3(%rbx,%rbx,2), %r8
	jmp	.L1
	.p2align 4,,10
	.p2align 3
.L16:
	cmpq	%rsi, %r12
	setne	%r10b
	jmp	.L42
	.p2align 4,,10
	.p2align 3
.L17:
	imulq	$2000, %rsi, %rax
	addq	%r9, %rax
	movzbl	(%rax,%rcx), %edx
	jmp	.L45
.L12:
	imulq	$2000, %rsi, %rax
	leaq	0(%rbp,%rsi), %rdi
	addq	%r9, %rax
	cmpq	%rdi, %r12
	movzbl	(%rax,%rcx), %edx
	setne	%r10b
	movq	%rsi, %rax
	movq	%rdi, %rsi
	jmp	.L43
	.p2align 4,,10
	.p2align 3
.L18:
	imulq	$2000, %rsi, %rax
	addq	%r9, %rax
	cmpq	$10, %rcx
	movzbl	(%rax,%rcx), %edx
	setne	%r11b
	jmp	.L44
.L5:
	leaq	22010+kabe(%rip), %rsi
	leaq	(%r9,%rcx), %rax
	addq	%r10, %rdx
	leaq	-2000(%rsi), %rdi
	.p2align 4,,10
	.p2align 3
.L10:
	movb	$2, (%rsi)
	addq	$2000, %rsi
	addq	$2001, %rdi
	addq	$1, %rax
	movb	$4, -2001(%rdi)
	movb	$1, -1(%rax)
	cmpq	%rsi, %rdx
	jne	.L10
	jmp	.L8
	.p2align 4,,10
	.p2align 3
.L13:
	cmpq	$10, %rcx
	setne	%r11b
	jmp	.L33
	.cfi_endproc
.LFE35:
	.size	solve, .-solve
	.p2align 4
	.globl	gcd
	.type	gcd, @function
gcd:
.LFB36:
	.cfi_startproc
	endbr64
	movq	%rdi, %rax
	movq	%rsi, %rdx
	testq	%rsi, %rsi
	je	.L72
	.p2align 4,,10
	.p2align 3
.L71:
	movq	%rdx, %r8
	xorl	%edx, %edx
	divq	%r8
	movq	%r8, %rax
	testq	%rdx, %rdx
	jne	.L71
	movq	%r8, %rax
	ret
	.p2align 4,,10
	.p2align 3
.L72:
	movq	%rdi, %r8
	movq	%r8, %rax
	ret
	.cfi_endproc
.LFE36:
	.size	gcd, .-gcd
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC1:
	.string	"%lu%lu"
.LC2:
	.string	"%lu\n"
	.section	.text.startup,"ax",@progbits
	.p2align 4
	.globl	main
	.type	main, @function
main:
.LFB37:
	.cfi_startproc
	endbr64
	subq	$40, %rsp
	.cfi_def_cfa_offset 48
	leaq	.LC1(%rip), %rdi
	movq	%fs:40, %rax
	movq	%rax, 24(%rsp)
	xorl	%eax, %eax
	leaq	16(%rsp), %rdx
	leaq	8(%rsp), %rsi
	call	__isoc99_scanf@PLT
	movl	%eax, %r8d
	movl	$1, %eax
	cmpl	$2, %r8d
	jne	.L74
	movq	16(%rsp), %rdx
	movq	8(%rsp), %rsi
	testq	%rdx, %rdx
	je	.L80
	movq	%rsi, %rax
	.p2align 4,,10
	.p2align 3
.L77:
	movq	%rdx, %rcx
	xorl	%edx, %edx
	divq	%rcx
	movq	%rcx, %rax
	testq	%rdx, %rdx
	jne	.L77
.L76:
	subq	%rcx, %rsi
	movl	$1, %edi
	xorl	%eax, %eax
	leaq	(%rsi,%rsi,2), %rdx
	leaq	.LC2(%rip), %rsi
	call	__printf_chk@PLT
	xorl	%eax, %eax
.L74:
	movq	24(%rsp), %rdx
	subq	%fs:40, %rdx
	jne	.L84
	addq	$40, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 8
	ret
.L80:
	.cfi_restore_state
	movq	%rsi, %rcx
	jmp	.L76
.L84:
	call	__stack_chk_fail@PLT
	.cfi_endproc
.LFE37:
	.size	main, .-main
	.globl	kabe
	.bss
	.align 32
	.type	kabe, @object
	.size	kabe, 4000000
kabe:
	.zero	4000000
	.section	.rodata.cst16,"aM",@progbits,16
	.align 16
.LC0:
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.ident	"GCC: (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:

rule
	.file	"temp.c"
	.text
	.p2align 4
	.globl	solve
	.type	solve, @function
solve:
.LFB35:
	.cfi_startproc
	endbr64
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	leaq	kabe(%rip), %r9
	movl	$4000000, %edx
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	pushq	%r13
	.cfi_def_cfa_offset 32
	.cfi_offset 13, -32
	pushq	%r12
	.cfi_def_cfa_offset 40
	.cfi_offset 12, -40
	movq	%rsi, %r12
	xorl	%esi, %esi
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	movq	%rdi, %rbx
	movq	%r9, %rdi
	subq	$8, %rsp
	.cfi_def_cfa_offset 64
	call	memset@PLT
	cmpq	$1000, %rbx
	ja	.L2
	movq	%rax, %r9
	testq	%rbx, %rbx
	je	.L8
	imulq	$2001, %rbx, %rsi
	leaq	10(%rbx), %rdi
	imulq	$2000, %rbx, %r10
	leaq	20010(%rax,%rsi), %rbp
	leaq	20010+kabe(%rip), %rax
	addq	$18010, %rsi
	leaq	20010(%r10), %rcx
	cmpq	%rax, %rbp
	leaq	20011(%r10), %r11
	setbe	%r8b
	cmpq	%rcx, %rsi
	setle	%dl
	orl	%edx, %r8d
	leaq	2000(%rax), %rdx
	cmpq	%rdx, %rbp
	setbe	%bpl
	cmpq	%r11, %rcx
	setge	%r13b
	orl	%r13d, %ebp
	andl	%ebp, %r8d
	leaq	-1(%rbx), %rbp
	cmpq	$21, %rbp
	seta	%bpl
	testb	%bpl, %r8b
	je	.L5
	addq	%r9, %rsi
	cmpq	%rdx, %rsi
	leaq	(%r9,%r11), %rsi
	setbe	%r8b
	cmpq	%rax, %rsi
	setbe	%sil
	orb	%sil, %r8b
	je	.L5
	movq	%rbx, %rsi
	addq	%r9, %rcx
	movdqa	.LC0(%rip), %xmm0
	andq	$-16, %rsi
	addq	%rcx, %rsi
	.p2align 4,,10
	.p2align 3
.L6:
	movb	$2, (%rdx)
	addq	$16, %rcx
	addq	$32016, %rax
	addq	$32000, %rdx
	movb	$2, -30000(%rdx)
	movb	$2, -28000(%rdx)
	movb	$2, -26000(%rdx)
	movb	$2, -24000(%rdx)
	movb	$2, -22000(%rdx)
	movb	$2, -20000(%rdx)
	movb	$2, -18000(%rdx)
	movb	$2, -16000(%rdx)
	movb	$2, -14000(%rdx)
	movb	$2, -12000(%rdx)
	movb	$2, -10000(%rdx)
	movb	$2, -8000(%rdx)
	movb	$2, -6000(%rdx)
	movb	$2, -4000(%rdx)
	movb	$2, -2000(%rdx)
	movb	$4, -32016(%rax)
	movb	$4, -30015(%rax)
	movb	$4, -28014(%rax)
	movb	$4, -26013(%rax)
	movb	$4, -24012(%rax)
	movb	$4, -22011(%rax)
	movb	$4, -20010(%rax)
	movb	$4, -18009(%rax)
	movb	$4, -16008(%rax)
	movb	$4, -14007(%rax)
	movb	$4, -12006(%rax)
	movb	$4, -10005(%rax)
	movb	$4, -8004(%rax)
	movb	$4, -6003(%rax)
	movb	$4, -4002(%rax)
	movb	$4, -2001(%rax)
	movups	%xmm0, -16(%rcx)
	cmpq	%rsi, %rcx
	jne	.L6
	movq	%rbx, %rax
	andq	$-16, %rax
	testb	$15, %bl
	je	.L8
	leaq	11(%rax), %rsi
	leaq	10(%rax), %r10
	imulq	$2000, %rsi, %rdx
	leaq	2(%rax), %rcx
	movb	$2, 10(%r9,%rdx)
	imulq	$2001, %r10, %rdx
	movb	$4, (%r9,%rdx)
	imulq	$2000, %rdi, %rdx
	addq	%r9, %rdx
	movb	$1, 10(%rax,%rdx)
	cmpq	%rcx, %rbx
	jb	.L8
	leaq	12(%rax), %r8
	imulq	$2000, %r8, %rcx
	movb	$2, 10(%r9,%rcx)
	imulq	$2001, %rsi, %rcx
	movb	$4, (%r9,%rcx)
	leaq	3(%rax), %rcx
	movb	$1, 11(%rax,%rdx)
	cmpq	%rcx, %rbx
	jb	.L8
	leaq	13(%rax), %r11
	imulq	$2000, %r11, %rcx
	movb	$2, 10(%r9,%rcx)
	imulq	$2001, %r8, %rcx
	movb	$4, (%r9,%rcx)
	leaq	4(%rax), %rcx
	movb	$1, 12(%rax,%rdx)
	cmpq	%rcx, %rbx
	jb	.L8
	leaq	14(%rax), %rbp
	imulq	$2000, %rbp, %rcx
	movb	$2, 10(%r9,%rcx)
	imulq	$2001, %r11, %rcx
	movb	$4, (%r9,%rcx)
	leaq	5(%rax), %rcx
	movb	$1, 13(%rax,%rdx)
	cmpq	%rcx, %rbx
	jb	.L8
	leaq	15(%rax), %r13
	imulq	$2000, %r13, %rcx
	movb	$2, 10(%r9,%rcx)
	imulq	$2001, %rbp, %rcx
	movb	$4, (%r9,%rcx)
	leaq	6(%rax), %rcx
	movb	$1, 14(%rax,%rdx)
	cmpq	%rcx, %rbx
	jb	.L8
	leaq	16(%rax), %rcx
	imulq	$2000, %rcx, %r14
	movb	$2, 10(%r9,%r14)
	imulq	$2001, %r13, %r14
	movb	$4, (%r9,%r14)
	leaq	7(%rax), %r14
	movb	$1, 15(%rax,%rdx)
	cmpq	%r14, %rbx
	jb	.L8
	leaq	17(%rax), %r14
	imulq	$2000, %r14, %r15
	movb	$2, 10(%r9,%r15)
	imulq	$2001, %rcx, %r15
	leaq	8(%rax), %rcx
	movb	$4, (%r9,%r15)
	movb	$1, 16(%rax,%rdx)
	cmpq	%rcx, %rbx
	jb	.L8
	leaq	18(%rax), %rcx
	imulq	$2000, %rcx, %r15
	movb	$2, 10(%r9,%r15)
	imulq	$2001, %r14, %r15
	movb	$4, (%r9,%r15)
	movb	$1, 17(%rax,%rdx)
	leaq	9(%rax), %rdx
	cmpq	%rdx, %rbx
	jb	.L8
	leaq	19(%rax), %r14
	imulq	$2000, %r14, %rdx
	movb	$2, 10(%r9,%rdx)
	imulq	$2001, %rcx, %rdx
	movb	$4, (%r9,%rdx)
	imulq	$2000, %rdi, %rdx
	addq	%r9, %rdx
	movb	$1, 18(%rax,%rdx)
	cmpq	%r10, %rbx
	jb	.L8
	leaq	20(%rax), %rcx
	imulq	$2000, %rcx, %rdi
	movb	$2, 10(%r9,%rdi)
	imulq	$2001, %r14, %rdi
	movb	$4, (%r9,%rdi)
	movb	$1, 19(%rax,%rdx)
	cmpq	%rsi, %rbx
	jb	.L8
	leaq	21(%rax), %rsi
	imulq	$2000, %rsi, %rdi
	movb	$2, 10(%r9,%rdi)
	imulq	$2001, %rcx, %rdi
	movb	$4, (%r9,%rdi)
	movb	$1, 20(%rax,%rdx)
	cmpq	%r8, %rbx
	jb	.L8
	leaq	22(%rax), %rcx
	imulq	$2000, %rcx, %rdi
	movb	$2, 10(%r9,%rdi)
	imulq	$2001, %rsi, %rdi
	movb	$4, (%r9,%rdi)
	movb	$1, 21(%rax,%rdx)
	cmpq	%r11, %rbx
	jb	.L8
	leaq	23(%rax), %rsi
	imulq	$2000, %rsi, %rdi
	movb	$2, 10(%r9,%rdi)
	imulq	$2001, %rcx, %rdi
	movb	$4, (%r9,%rdi)
	movb	$1, 22(%rax,%rdx)
	cmpq	%rbp, %rbx
	jb	.L8
	leaq	24(%rax), %rcx
	imulq	$2000, %rcx, %rdi
	movb	$2, 10(%r9,%rdi)
	imulq	$2001, %rsi, %rdi
	movb	$4, (%r9,%rdi)
	movb	$1, 23(%rax,%rdx)
	cmpq	%r13, %rbx
	jb	.L8
	addq	$25, %rax
	imulq	$2000, %rax, %rax
	movb	$2, 10(%r9,%rax)
	imulq	$2001, %rcx, %rax
	movb	$4, (%r9,%rax)
	movb	$1, (%rdx,%rcx)
	.p2align 4,,10
	.p2align 3
.L8:
	addq	$10, %r12
	movl	$1, %ebx
	xorl	%ebp, %ebp
	xorl	%r8d, %r8d
	movq	%r12, %rsi
	xorl	%eax, %eax
	movl	$10, %ecx
	leaq	.L14(%rip), %r14
	leaq	.L29(%rip), %r13
	.p2align 4,,10
	.p2align 3
.L60:
	cmpl	$5, %eax
	ja	.L12
	movslq	(%r14,%rax,4), %rax
	addq	%r14, %rax
	notrack jmp	*%rax
	.section	.rodata
	.align 4
	.align 4
.L14:
	.long	.L12-.L14
	.long	.L18-.L14
	.long	.L17-.L14
	.long	.L16-.L14
	.long	.L15-.L14
	.long	.L13-.L14
	.text
	.p2align 4,,10
	.p2align 3
.L23:
	testb	%dil, %dil
	je	.L1
.L15:
	subq	$1, %rsi
	subq	$1, %rcx
	movq	$-1, %rbx
	movq	$-1, %rbp
	imulq	$2000, %rsi, %rax
	addq	%r9, %rax
	addq	%rcx, %rax
	movzbl	(%rax), %edx
	orl	$4, %edx
	cmpq	$10, %rcx
	setne	%r11b
	cmpq	%r12, %rsi
	movb	%dl, (%rax)
	movl	$4, %eax
	setne	%r10b
.L19:
	addq	$1, %r8
	testb	$1, %dl
	jne	.L20
.L68:
	imulq	$2000, %rsi, %rdi
	addq	%r9, %rdi
	testb	$1, -1(%rcx,%rdi)
	jne	.L20
.L21:
	testb	$2, %dl
	jne	.L26
	leaq	1(%rsi), %rdi
	imulq	$2000, %rdi, %rdi
	addq	%r9, %rdi
	testb	$2, (%rdi,%rcx)
	je	.L27
.L26:
	testq	%r8, %r8
	movl	%r11d, %edi
	sete	%r15b
	orl	%r10d, %edi
	orl	%edi, %r15d
	cmpl	$5, %eax
	ja	.L28
	movl	%eax, %edi
	movslq	0(%r13,%rdi,4), %rdi
	addq	%r13, %rdi
	notrack jmp	*%rdi
	.section	.rodata
	.align 4
	.align 4
.L29:
	.long	.L28-.L29
	.long	.L27-.L29
	.long	.L32-.L29
	.long	.L31-.L29
	.long	.L30-.L29
	.long	.L27-.L29
	.text
	.p2align 4,,10
	.p2align 3
.L27:
	testb	$4, %dl
	jne	.L35
	leaq	-1(%rsi), %rdi
	imulq	$2000, %rdi, %rdi
	addq	%r9, %rdi
	testb	$4, -1(%rcx,%rdi)
	jne	.L35
.L36:
	testq	%r8, %r8
	je	.L60
	orb	%r11b, %r10b
	jne	.L60
.L1:
	addq	$8, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 56
	movq	%r8, %rax
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%rbp
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r13
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	ret
	.p2align 4,,10
	.p2align 3
.L30:
	.cfi_restore_state
	xorl	%ebp, %ebp
	movl	$1, %ebx
	testb	%r15b, %r15b
	je	.L1
.L47:
	movq	%rsi, %rax
.L43:
	imulq	$2000, %rax, %rax
	orl	$1, %edx
	addq	%r9, %rax
	movb	%dl, (%rax,%rcx)
	imulq	$2000, %rsi, %rax
	addq	%rbx, %rcx
	addq	%r9, %rax
	cmpq	$10, %rcx
	movzbl	(%rax,%rcx), %edx
	setne	%r11b
	xorl	%eax, %eax
	addq	$1, %r8
	testb	$1, %dl
	je	.L68
	.p2align 4,,10
	.p2align 3
.L20:
	testq	%r8, %r8
	movl	%r11d, %r15d
	sete	%dil
	orl	%r10d, %r15d
	orl	%r15d, %edi
	cmpl	$4, %eax
	je	.L39
	cmpl	$5, %eax
	je	.L23
	cmpl	$1, %eax
	je	.L24
	cmpl	$2, %eax
	jne	.L21
.L25:
	testb	%dil, %dil
	je	.L1
.L44:
	imulq	$2000, %rsi, %rax
	orl	$2, %edx
	subq	$1, %rsi
	movq	$-1, %rbp
	addq	%r9, %rax
	movb	%dl, (%rax,%rcx)
	imulq	$2000, %rsi, %rax
	addq	%r9, %rax
	cmpq	%rsi, %r12
	movzbl	(%rax,%rcx), %edx
	setne	%r10b
	movl	$1, %eax
	xorl	%ebx, %ebx
	jmp	.L19
	.p2align 4,,10
	.p2align 3
.L31:
	testb	%r15b, %r15b
	je	.L1
.L45:
	imulq	$2000, %rsi, %rax
	orl	$4, %edx
	addq	$1, %rsi
	movl	$1, %ebx
	movl	$1, %ebp
	addq	%r9, %rax
	movb	%dl, (%rax,%rcx)
	imulq	$2000, %rsi, %rax
	addq	$1, %rcx
	addq	%r9, %rax
	cmpq	$10, %rcx
	setne	%r11b
	cmpq	%rsi, %r12
	movzbl	(%rax,%rcx), %edx
	movl	$2, %eax
	setne	%r10b
	jmp	.L19
	.p2align 4,,10
	.p2align 3
.L32:
	testb	%r15b, %r15b
	je	.L1
.L42:
	imulq	$2000, %rsi, %rax
	subq	$1, %rcx
	movq	$-1, %rbx
	addq	%r9, %rax
	addq	%rcx, %rax
	movzbl	(%rax), %edx
	orl	$1, %edx
	cmpq	$10, %rcx
	movb	%dl, (%rax)
	setne	%r11b
	movl	$3, %eax
	xorl	%ebp, %ebp
	jmp	.L19
	.p2align 4,,10
	.p2align 3
.L35:
	testq	%r8, %r8
	movl	%r11d, %r15d
	sete	%dil
	orl	%r10d, %r15d
	orl	%r15d, %edi
	cmpl	$3, %eax
	je	.L25
	jg	.L38
	testl	%eax, %eax
	je	.L39
	cmpl	$1, %eax
	jne	.L36
	testb	%dil, %dil
	jne	.L42
	jmp	.L1
	.p2align 4,,10
	.p2align 3
.L38:
	cmpl	$5, %eax
	jne	.L36
	xorl	%ebp, %ebp
	movl	$1, %ebx
	testb	%dil, %dil
	jne	.L47
	jmp	.L1
	.p2align 4,,10
	.p2align 3
.L39:
	testb	%dil, %dil
	je	.L1
.L33:
	addq	$1, %rsi
	movl	$1, %ebp
	imulq	$2000, %rsi, %rax
	addq	%r9, %rax
	addq	%rcx, %rax
	movzbl	(%rax), %edx
	orl	$2, %edx
	cmpq	%r12, %rsi
	movb	%dl, (%rax)
	setne	%r10b
	movl	$5, %eax
	xorl	%ebx, %ebx
	jmp	.L19
	.p2align 4,,10
	.p2align 3
.L24:
	testb	%dil, %dil
	jne	.L45
	jmp	.L1
	.p2align 4,,10
	.p2align 3
.L28:
	testb	%r15b, %r15b
	jne	.L15
	jmp	.L1
	.p2align 4,,10
	.p2align 3
.L2:
	leaq	-3(%rbx,%rbx,2), %r8
	jmp	.L1
	.p2align 4,,10
	.p2align 3
.L16:
	cmpq	%rsi, %r12
	setne	%r10b
	jmp	.L42
	.p2align 4,,10
	.p2align 3
.L17:
	imulq	$2000, %rsi, %rax
	addq	%r9, %rax
	movzbl	(%rax,%rcx), %edx
	jmp	.L45
.L12:
	imulq	$2000, %rsi, %rax
	leaq	0(%rbp,%rsi), %rdi
	addq	%r9, %rax
	cmpq	%rdi, %r12
	movzbl	(%rax,%rcx), %edx
	setne	%r10b
	movq	%rsi, %rax
	movq	%rdi, %rsi
	jmp	.L43
	.p2align 4,,10
	.p2align 3
.L18:
	imulq	$2000, %rsi, %rax
	addq	%r9, %rax
	cmpq	$10, %rcx
	movzbl	(%rax,%rcx), %edx
	setne	%r11b
	jmp	.L44
.L5:
	leaq	22010+kabe(%rip), %rsi
	leaq	(%r9,%rcx), %rax
	addq	%r10, %rdx
	leaq	-2000(%rsi), %rdi
	.p2align 4,,10
	.p2align 3
.L10:
	movb	$2, (%rsi)
	addq	$2000, %rsi
	addq	$2001, %rdi
	addq	$1, %rax
	movb	$4, -2001(%rdi)
	movb	$1, -1(%rax)
	cmpq	%rsi, %rdx
	jne	.L10
	jmp	.L8
	.p2align 4,,10
	.p2align 3
.L13:
	cmpq	$10, %rcx
	setne	%r11b
	jmp	.L33
	.cfi_endproc
.LFE35:
	.size	solve, .-solve
	.p2align 4
	.globl	gcd
	.type	gcd, @function
gcd:
.LFB36:
	.cfi_startproc
	endbr64
	movq	%rdi, %rax
	movq	%rsi, %rdx
	testq	%rsi, %rsi
	je	.L72
	.p2align 4,,10
	.p2align 3
.L71:
	movq	%rdx, %r8
	xorl	%edx, %edx
	divq	%r8
	movq	%r8, %rax
	testq	%rdx, %rdx
	jne	.L71
	movq	%r8, %rax
	ret
	.p2align 4,,10
	.p2align 3
.L72:
	movq	%rdi, %r8
	movq	%r8, %rax
	ret
	.cfi_endproc
.LFE36:
	.size	gcd, .-gcd
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC1:
	.string	"%lu%lu"
.LC2:
	.string	"%lu\n"
	.section	.text.startup,"ax",@progbits
	.p2align 4
	.globl	main
	.type	main, @function
main:
.LFB37:
	.cfi_startproc
	endbr64
	subq	$40, %rsp
	.cfi_def_cfa_offset 48
	leaq	.LC1(%rip), %rdi
	movq	%fs:40, %rax
	movq	%rax, 24(%rsp)
	xorl	%eax, %eax
	leaq	16(%rsp), %rdx
	leaq	8(%rsp), %rsi
	call	__isoc99_scanf@PLT
	movl	%eax, %r8d
	movl	$1, %eax
	cmpl	$2, %r8d
	jne	.L74
	movq	16(%rsp), %rdx
	movq	8(%rsp), %rsi
	testq	%rdx, %rdx
	je	.L80
	movq	%rsi, %rax
	.p2align 4,,10
	.p2align 3
.L77:
	movq	%rdx, %rcx
	xorl	%edx, %edx
	divq	%rcx
	movq	%rcx, %rax
	testq	%rdx, %rdx
	jne	.L77
.L76:
	subq	%rcx, %rsi
	movl	$1, %edi
	xorl	%eax, %eax
	leaq	(%rsi,%rsi,2), %rdx
	leaq	.LC2(%rip), %rsi
	call	__printf_chk@PLT
	xorl	%eax, %eax
.L74:
	movq	24(%rsp), %rdx
	subq	%fs:40, %rdx
	jne	.L84
	addq	$40, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 8
	ret
.L80:
	.cfi_restore_state
	movq	%rsi, %rcx
	jmp	.L76
.L84:
	call	__stack_chk_fail@PLT
	.cfi_endproc
.LFE37:
	.size	main, .-main
	.globl	kabe
	.bss
	.align 32
	.type	kabe, @object
	.size	kabe, 4000000
kabe:
	.zero	4000000
	.section	.rodata.cst16,"aM",@progbits,16
	.align 16
.LC0:
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.byte	1
	.ident	"GCC: (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:

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

/*
答えはXに依存しないと予想できる -> はずれ

N=2 len=3
N=3 len=6
N=4 len=9 (X=2 -> len=6)
N=5 len=12

*/

#define KABE_MIGI 1
#define KABE_UE 2
#define KABE_SITA 4

char kabe[2000][2000];

uint64_t solve(uint64_t N, uint64_t X) {
	memset(kabe, 0, sizeof(kabe));
	if (N <= 1000) {
		static const uint64_t dputtern[6][2] = {
			{0, 1}, /* 右 */
			{-1, 0}, /* 右上 */
			{1, 1}, /* 右下 */
			{0, -1}, /* 左 */
			{-1, -1}, /* 左上 */
			{1, 0} /* 左下 */
		};
		uint64_t i;
		uint64_t y, x;
		int d;
		int invalid;
		uint64_t answer = 0;
		for (i = 1; i <= N; i++) {
			kabe[10+i][10+0] = KABE_UE; /* 左 */
			kabe[10+i - 1][10+i - 1] = KABE_SITA; /* 右 */
			kabe[10+N][10+i - 1] = KABE_MIGI; /* 底辺 */
		}
		y = 10+X;
		x = 10;
		d = 0; /* 右 */
		while (answer == 0 || y != 10+X || x != 10) {
			/* 壁を生やして移動する */
			switch(d) {
				case 0: kabe[y][x] |= KABE_MIGI; break;
				case 1: kabe[y][x] |= KABE_UE; break;
				case 2: kabe[y][x] |= KABE_SITA; break;
				case 3: kabe[y][x-1] |= KABE_MIGI; break;
				case 4: kabe[y-1][x-1] |= KABE_SITA; break;
				case 5: kabe[y+1][x] |= KABE_UE; break;
			}
			y += dputtern[d][0];
			x += dputtern[d][1];
			answer++;
#if 0
			printf("%d %d %d %d\n", (int)(x-10),(int)(y-10),d, kabe[y][x]);fflush(stdout);
			if(answer>20)break;
#endif
			/* 反射する */
			invalid = 1;
			if ((kabe[y][x] & KABE_MIGI) || (kabe[y][x-1] & KABE_MIGI)) {
				invalid = 0;
				switch(d) {
					case 0: invalid = 1; break;
					case 1: d = 2; break;
					case 2: d = 1; break;
					case 3: invalid = 1; break;
					case 4: d = 5; break;
					case 5: d = 4; break;
				}
			}
			if (invalid && ((kabe[y][x] & KABE_UE) || (kabe[y+1][x] & KABE_UE))) {
				invalid = 0;
				switch(d) {
					case 0: d = 4; break;
					case 1: invalid = 1; break;
					case 2: d = 3; break;
					case 3: d = 2; break;
					case 4: d = 0; break;
					case 5: invalid = 1; break;
				}
			}
			if (invalid && ((kabe[y][x] & KABE_SITA) || (kabe[y-1][x-1] & KABE_SITA))) {
				switch(d) {
					case 0: d = 5; break;
					case 1: d = 3; break;
					case 2: invalid = 1; break;
					case 3: d = 1; break;
					case 4: invalid = 1; break;
					case 5: d = 0; break;
				}
			}
		}
		return answer;
	} else {
		/* not implemented */
		return  UINT64_C(3) * (N - 1);
	}
}

uint64_t gcd(uint64_t a, uint64_t b) {
	uint64_t r;
	while (b) {
		r = a % b;
		a = b;
		b = r;
	}
	return a;
}

int main(void) {
	uint64_t N, X;
#if 0
	int wacount = 0;
	for (N = 2; N < 200; N++) {
		for (X = 1; X < N; X++) {
			uint64_t a = solve(N, X);
			uint64_t p = UINT64_C(3) * (N - gcd(N, X));
			if (a != p) {
				printf("Wrong answer N = %"PRIu64", X = %"PRIu64", a = %"PRIu64", p = %"PRIu64"\n", N, X, a, p);
				if (++wacount >= 10) return 0;
			}
		}
	}
#else
	if (scanf("%"SCNu64"%"SCNu64, &N, &X) != 2) return 1;
#if 0
	printf("%"PRIu64"\n", solve(N, X));
#else
	printf("%"PRIu64"\n", UINT64_C(3) * (N - gcd(N, X)));
#endif
#endif
	return 0;
}

5 4
 7 4
 6 1
 9 4
 6 3
 14 4
 8 1
 28 4
 15 2
 28 3

12
 18
 15
 24
 9
 36
 21
 72
 42
 81

Given the following C code and unoptimized assembly code, your task is to generate highly optimized x86-64 assembly code.
C Code:

```c
#include <stdio.h>
#include <string.h>
#include <inttypes.h>

/*
答えはXに依存しないと予想できる -> はずれ

N=2 len=3
N=3 len=6
N=4 len=9 (X=2 -> len=6)
N=5 len=12

*/

#define KABE_MIGI 1
#define KABE_UE 2
#define KABE_SITA 4

char kabe[2000][2000];

uint64_t solve(uint64_t N, uint64_t X) {
	memset(kabe, 0, sizeof(kabe));
	if (N <= 1000) {
		static const uint64_t dputtern[6][2] = {
			{0, 1}, /* 右 */
			{-1, 0}, /* 右上 */
			{1, 1}, /* 右下 */
			{0, -1}, /* 左 */
			{-1, -1}, /* 左上 */
			{1, 0} /* 左下 */
		};
		uint64_t i;
		uint64_t y, x;
		int d;
		int invalid;
		uint64_t answer = 0;
		for (i = 1; i <= N; i++) {
			kabe[10+i][10+0] = KABE_UE; /* 左 */
			kabe[10+i - 1][10+i - 1] = KABE_SITA; /* 右 */
			kabe[10+N][10+i - 1] = KABE_MIGI; /* 底辺 */
		}
		y = 10+X;
		x = 10;
		d = 0; /* 右 */
		while (answer == 0 || y != 10+X || x != 10) {
			/* 壁を生やして移動する */
			switch(d) {
				case 0: kabe[y][x] |= KABE_MIGI; break;
				case 1: kabe[y][x] |= KABE_UE; break;
				case 2: kabe[y][x] |= KABE_SITA; break;
				case 3: kabe[y][x-1] |= KABE_MIGI; break;
				case 4: kabe[y-1][x-1] |= KABE_SITA; break;
				case 5: kabe[y+1][x] |= KABE_UE; break;
			}
			y += dputtern[d][0];
			x += dputtern[d][1];
			answer++;
#if 0
			printf("%d %d %d %d\n", (int)(x-10),(int)(y-10),d, kabe[y][x]);fflush(stdout);
			if(answer>20)break;
#endif
			/* 反射する */
			invalid = 1;
			if ((kabe[y][x] & KABE_MIGI) || (kabe[y][x-1] & KABE_MIGI)) {
				invalid = 0;
				switch(d) {
					case 0: invalid = 1; break;
					case 1: d = 2; break;
					case 2: d = 1; break;
					case 3: invalid = 1; break;
					case 4: d = 5; break;
					case 5: d = 4; break;
				}
			}
			if (invalid && ((kabe[y][x] & KABE_UE) || (kabe[y+1][x] & KABE_UE))) {
				invalid = 0;
				switch(d) {
					case 0: d = 4; break;
					case 1: invalid = 1; break;
					case 2: d = 3; break;
					case 3: d = 2; break;
					case 4: d = 0; break;
					case 5: invalid = 1; break;
				}
			}
			if (invalid && ((kabe[y][x] & KABE_SITA) || (kabe[y-1][x-1] & KABE_SITA))) {
				switch(d) {
					case 0: d = 5; break;
					case 1: d = 3; break;
					case 2: invalid = 1; break;
					case 3: d = 1; break;
					case 4: invalid = 1; break;
					case 5: d = 0; break;
				}
			}
		}
		return answer;
	} else {
		/* not implemented */
		return  UINT64_C(3) * (N - 1);
	}
}

uint64_t gcd(uint64_t a, uint64_t b) {
	uint64_t r;
	while (b) {
		r = a % b;
		a = b;
		b = r;
	}
	return a;
}

int main(void) {
	uint64_t N, X;
#if 0
	int wacount = 0;
	for (N = 2; N < 200; N++) {
		for (X = 1; X < N; X++) {
			uint64_t a = solve(N, X);
			uint64_t p = UINT64_C(3) * (N - gcd(N, X));
			if (a != p) {
				printf("Wrong answer N = %"PRIu64", X = %"PRIu64", a = %"PRIu64", p = %"PRIu64"\n", N, X, a, p);
				if (++wacount >= 10) return 0;
			}
		}
	}
#else
	if (scanf("%"SCNu64"%"SCNu64, &N, &X) != 2) return 1;
#if 0
	printf("%"PRIu64"\n", solve(N, X));
#else
	printf("%"PRIu64"\n", UINT64_C(3) * (N - gcd(N, X)));
#endif
#endif
	return 0;
}
```

Unoptimized Assembly Code:

```assembly
	.file	"temp.c"
	.text
	.globl	kabe
	.bss
	.align 32
	.type	kabe, @object
	.size	kabe, 4000000
kabe:
	.zero	4000000
	.text
	.globl	solve
	.type	solve, @function
solve:
.LFB0:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$64, %rsp
	movq	%rdi, -56(%rbp)
	movq	%rsi, -64(%rbp)
	movl	$4000000, %edx
	movl	$0, %esi
	leaq	kabe(%rip), %rax
	movq	%rax, %rdi
	call	memset@PLT
	cmpq	$1000, -56(%rbp)
	ja	.L2
	movq	$0, -8(%rbp)
	movq	$1, -32(%rbp)
	jmp	.L3
.L4:
	movq	-32(%rbp), %rax
	addq	$10, %rax
	imulq	$2000, %rax, %rax
	leaq	10+kabe(%rip), %rdx
	movb	$2, (%rax,%rdx)
	movq	-32(%rbp), %rax
	leaq	9(%rax), %rdx
	movq	-32(%rbp), %rax
	leaq	9(%rax), %rcx
	imulq	$2000, %rdx, %rax
	leaq	(%rax,%rcx), %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movb	$4, (%rax)
	movq	-56(%rbp), %rax
	leaq	10(%rax), %rdx
	movq	-32(%rbp), %rax
	leaq	9(%rax), %rcx
	imulq	$2000, %rdx, %rax
	leaq	(%rax,%rcx), %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movb	$1, (%rax)
	addq	$1, -32(%rbp)
.L3:
	movq	-32(%rbp), %rax
	cmpq	-56(%rbp), %rax
	jbe	.L4
	movq	-64(%rbp), %rax
	addq	$10, %rax
	movq	%rax, -24(%rbp)
	movq	$10, -16(%rbp)
	movl	$0, -40(%rbp)
	nop
	jmp	.L32
.L41:
	cmpl	$5, -40(%rbp)
	ja	.L6
	movl	-40(%rbp), %eax
	leaq	0(,%rax,4), %rdx
	leaq	.L8(%rip), %rax
	movl	(%rdx,%rax), %eax
	cltq
	leaq	.L8(%rip), %rdx
	addq	%rdx, %rax
	notrack jmp	*%rax
	.section	.rodata
	.align 4
	.align 4
.L8:
	.long	.L13-.L8
	.long	.L12-.L8
	.long	.L11-.L8
	.long	.L10-.L8
	.long	.L9-.L8
	.long	.L7-.L8
	.text
.L13:
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	orl	$1, %eax
	movl	%eax, %edx
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rcx
	movq	-16(%rbp), %rax
	addq	%rax, %rcx
	leaq	kabe(%rip), %rax
	addq	%rcx, %rax
	movb	%dl, (%rax)
	jmp	.L6
.L12:
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	orl	$2, %eax
	movl	%eax, %edx
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rcx
	movq	-16(%rbp), %rax
	addq	%rax, %rcx
	leaq	kabe(%rip), %rax
	addq	%rcx, %rax
	movb	%dl, (%rax)
	jmp	.L6
.L11:
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	orl	$4, %eax
	movl	%eax, %edx
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rcx
	movq	-16(%rbp), %rax
	addq	%rax, %rcx
	leaq	kabe(%rip), %rax
	addq	%rcx, %rax
	movb	%dl, (%rax)
	jmp	.L6
.L10:
	movq	-16(%rbp), %rax
	leaq	-1(%rax), %rdx
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movq	-16(%rbp), %rdx
	leaq	-1(%rdx), %rcx
	orl	$1, %eax
	movl	%eax, %edx
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rax
	addq	%rax, %rcx
	leaq	kabe(%rip), %rax
	addq	%rcx, %rax
	movb	%dl, (%rax)
	jmp	.L6
.L9:
	movq	-24(%rbp), %rax
	leaq	-1(%rax), %rdx
	movq	-16(%rbp), %rax
	leaq	-1(%rax), %rcx
	imulq	$2000, %rdx, %rax
	leaq	(%rax,%rcx), %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movq	-24(%rbp), %rdx
	leaq	-1(%rdx), %rcx
	movq	-16(%rbp), %rdx
	leaq	-1(%rdx), %rsi
	orl	$4, %eax
	movl	%eax, %edx
	imulq	$2000, %rcx, %rax
	leaq	(%rax,%rsi), %rcx
	leaq	kabe(%rip), %rax
	addq	%rcx, %rax
	movb	%dl, (%rax)
	jmp	.L6
.L7:
	movq	-24(%rbp), %rax
	addq	$1, %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movq	-24(%rbp), %rdx
	leaq	1(%rdx), %rcx
	orl	$2, %eax
	movl	%eax, %edx
	imulq	$2000, %rcx, %rcx
	movq	-16(%rbp), %rax
	addq	%rax, %rcx
	leaq	kabe(%rip), %rax
	addq	%rcx, %rax
	movb	%dl, (%rax)
	nop
.L6:
	movl	-40(%rbp), %eax
	cltq
	salq	$4, %rax
	movq	%rax, %rdx
	leaq	dputtern.0(%rip), %rax
	movq	(%rdx,%rax), %rax
	addq	%rax, -24(%rbp)
	movl	-40(%rbp), %eax
	cltq
	salq	$4, %rax
	movq	%rax, %rdx
	leaq	8+dputtern.0(%rip), %rax
	movq	(%rdx,%rax), %rax
	addq	%rax, -16(%rbp)
	addq	$1, -8(%rbp)
	movl	$1, -36(%rbp)
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movsbl	%al, %eax
	andl	$1, %eax
	testl	%eax, %eax
	jne	.L14
	movq	-16(%rbp), %rax
	leaq	-1(%rax), %rdx
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movsbl	%al, %eax
	andl	$1, %eax
	testl	%eax, %eax
	je	.L15
.L14:
	movl	$0, -36(%rbp)
	cmpl	$5, -40(%rbp)
	ja	.L15
	movl	-40(%rbp), %eax
	leaq	0(,%rax,4), %rdx
	leaq	.L17(%rip), %rax
	movl	(%rdx,%rax), %eax
	cltq
	leaq	.L17(%rip), %rdx
	addq	%rdx, %rax
	notrack jmp	*%rax
	.section	.rodata
	.align 4
	.align 4
.L17:
	.long	.L22-.L17
	.long	.L21-.L17
	.long	.L20-.L17
	.long	.L19-.L17
	.long	.L18-.L17
	.long	.L16-.L17
	.text
.L22:
	movl	$1, -36(%rbp)
	jmp	.L15
.L21:
	movl	$2, -40(%rbp)
	jmp	.L15
.L20:
	movl	$1, -40(%rbp)
	jmp	.L15
.L19:
	movl	$1, -36(%rbp)
	jmp	.L15
.L18:
	movl	$5, -40(%rbp)
	jmp	.L15
.L16:
	movl	$4, -40(%rbp)
	nop
.L15:
	cmpl	$0, -36(%rbp)
	je	.L23
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movsbl	%al, %eax
	andl	$2, %eax
	testl	%eax, %eax
	jne	.L24
	movq	-24(%rbp), %rax
	addq	$1, %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movsbl	%al, %eax
	andl	$2, %eax
	testl	%eax, %eax
	je	.L23
.L24:
	movl	$0, -36(%rbp)
	cmpl	$5, -40(%rbp)
	ja	.L23
	movl	-40(%rbp), %eax
	leaq	0(,%rax,4), %rdx
	leaq	.L26(%rip), %rax
	movl	(%rdx,%rax), %eax
	cltq
	leaq	.L26(%rip), %rdx
	addq	%rdx, %rax
	notrack jmp	*%rax
	.section	.rodata
	.align 4
	.align 4
.L26:
	.long	.L31-.L26
	.long	.L30-.L26
	.long	.L29-.L26
	.long	.L28-.L26
	.long	.L27-.L26
	.long	.L25-.L26
	.text
.L31:
	movl	$4, -40(%rbp)
	jmp	.L23
.L30:
	movl	$1, -36(%rbp)
	jmp	.L23
.L29:
	movl	$3, -40(%rbp)
	jmp	.L23
.L28:
	movl	$2, -40(%rbp)
	jmp	.L23
.L27:
	movl	$0, -40(%rbp)
	jmp	.L23
.L25:
	movl	$1, -36(%rbp)
	nop
.L23:
	cmpl	$0, -36(%rbp)
	je	.L32
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movsbl	%al, %eax
	andl	$4, %eax
	testl	%eax, %eax
	jne	.L33
	movq	-24(%rbp), %rax
	leaq	-1(%rax), %rdx
	movq	-16(%rbp), %rax
	leaq	-1(%rax), %rcx
	imulq	$2000, %rdx, %rax
	leaq	(%rax,%rcx), %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movsbl	%al, %eax
	andl	$4, %eax
	testl	%eax, %eax
	je	.L32
.L33:
	cmpl	$5, -40(%rbp)
	ja	.L32
	movl	-40(%rbp), %eax
	leaq	0(,%rax,4), %rdx
	leaq	.L35(%rip), %rax
	movl	(%rdx,%rax), %eax
	cltq
	leaq	.L35(%rip), %rdx
	addq	%rdx, %rax
	notrack jmp	*%rax
	.section	.rodata
	.align 4
	.align 4
.L35:
	.long	.L40-.L35
	.long	.L39-.L35
	.long	.L38-.L35
	.long	.L37-.L35
	.long	.L36-.L35
	.long	.L34-.L35
	.text
.L40:
	movl	$5, -40(%rbp)
	jmp	.L32
.L39:
	movl	$3, -40(%rbp)
	jmp	.L32
.L38:
	movl	$1, -36(%rbp)
	jmp	.L32
.L37:
	movl	$1, -40(%rbp)
	jmp	.L32
.L36:
	movl	$1, -36(%rbp)
	jmp	.L32
.L34:
	movl	$0, -40(%rbp)
	nop
.L32:
	cmpq	$0, -8(%rbp)
	je	.L41
	movq	-64(%rbp), %rax
	addq	$10, %rax
	cmpq	%rax, -24(%rbp)
	jne	.L41
	cmpq	$10, -16(%rbp)
	jne	.L41
	movq	-8(%rbp), %rax
	jmp	.L42
.L2:
	movq	-56(%rbp), %rdx
	movq	%rdx, %rax
	addq	%rax, %rax
	addq	%rdx, %rax
	subq	$3, %rax
.L42:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE0:
	.size	solve, .-solve
	.globl	gcd
	.type	gcd, @function
gcd:
.LFB1:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movq	%rdi, -24(%rbp)
	movq	%rsi, -32(%rbp)
	jmp	.L44
.L45:
	movq	-24(%rbp), %rax
	movl	$0, %edx
	divq	-32(%rbp)
	movq	%rdx, -8(%rbp)
	movq	-32(%rbp), %rax
	movq	%rax, -24(%rbp)
	movq	-8(%rbp), %rax
	movq	%rax, -32(%rbp)
.L44:
	cmpq	$0, -32(%rbp)
	jne	.L45
	movq	-24(%rbp), %rax
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE1:
	.size	gcd, .-gcd
	.section	.rodata
.LC0:
	.string	"%lu%lu"
.LC1:
	.string	"%lu\n"
	.text
	.globl	main
	.type	main, @function
main:
.LFB2:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	pushq	%rbx
	subq	$40, %rsp
	.cfi_offset 3, -24
	movq	%fs:40, %rax
	movq	%rax, -24(%rbp)
	xorl	%eax, %eax
	leaq	-32(%rbp), %rdx
	leaq	-40(%rbp), %rax
	movq	%rax, %rsi
	leaq	.LC0(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	cmpl	$2, %eax
	je	.L48
	movl	$1, %eax
	jmp	.L50
.L48:
	movq	-40(%rbp), %rbx
	movq	-32(%rbp), %rdx
	movq	-40(%rbp), %rax
	movq	%rdx, %rsi
	movq	%rax, %rdi
	call	gcd
	subq	%rax, %rbx
	movq	%rbx, %rdx
	movq	%rdx, %rax
	addq	%rax, %rax
	addq	%rdx, %rax
	movq	%rax, %rsi
	leaq	.LC1(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
	movl	$0, %eax
.L50:
	movq	-24(%rbp), %rdx
	subq	%fs:40, %rdx
	je	.L51
	call	__stack_chk_fail@PLT
.L51:
	movq	-8(%rbp), %rbx
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE2:
	.size	main, .-main
	.section	.rodata
	.align 32
	.type	dputtern.0, @object
	.size	dputtern.0, 96
dputtern.0:
	.quad	0
	.quad	1
	.quad	-1
	.quad	0
	.quad	1
	.quad	1
	.quad	0
	.quad	-1
	.quad	-1
	.quad	-1
	.quad	1
	.quad	0
	.ident	"GCC: (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:
```

Only output the optimized assembly code. Do not include any other text. Do not write any comments in the assembly code. Wrap the assembly code in ```assembly``` tags.
train
	.file	"temp.c"
	.text
	.globl	kabe
	.bss
	.align 32
	.type	kabe, @object
	.size	kabe, 4000000
kabe:
	.zero	4000000
	.text
	.globl	solve
	.type	solve, @function
solve:
.LFB0:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$64, %rsp
	movq	%rdi, -56(%rbp)
	movq	%rsi, -64(%rbp)
	movl	$4000000, %edx
	movl	$0, %esi
	leaq	kabe(%rip), %rax
	movq	%rax, %rdi
	call	memset@PLT
	cmpq	$1000, -56(%rbp)
	ja	.L2
	movq	$0, -8(%rbp)
	movq	$1, -32(%rbp)
	jmp	.L3
.L4:
	movq	-32(%rbp), %rax
	addq	$10, %rax
	imulq	$2000, %rax, %rax
	leaq	10+kabe(%rip), %rdx
	movb	$2, (%rax,%rdx)
	movq	-32(%rbp), %rax
	leaq	9(%rax), %rdx
	movq	-32(%rbp), %rax
	leaq	9(%rax), %rcx
	imulq	$2000, %rdx, %rax
	leaq	(%rax,%rcx), %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movb	$4, (%rax)
	movq	-56(%rbp), %rax
	leaq	10(%rax), %rdx
	movq	-32(%rbp), %rax
	leaq	9(%rax), %rcx
	imulq	$2000, %rdx, %rax
	leaq	(%rax,%rcx), %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movb	$1, (%rax)
	addq	$1, -32(%rbp)
.L3:
	movq	-32(%rbp), %rax
	cmpq	-56(%rbp), %rax
	jbe	.L4
	movq	-64(%rbp), %rax
	addq	$10, %rax
	movq	%rax, -24(%rbp)
	movq	$10, -16(%rbp)
	movl	$0, -40(%rbp)
	nop
	jmp	.L32
.L41:
	cmpl	$5, -40(%rbp)
	ja	.L6
	movl	-40(%rbp), %eax
	leaq	0(,%rax,4), %rdx
	leaq	.L8(%rip), %rax
	movl	(%rdx,%rax), %eax
	cltq
	leaq	.L8(%rip), %rdx
	addq	%rdx, %rax
	notrack jmp	*%rax
	.section	.rodata
	.align 4
	.align 4
.L8:
	.long	.L13-.L8
	.long	.L12-.L8
	.long	.L11-.L8
	.long	.L10-.L8
	.long	.L9-.L8
	.long	.L7-.L8
	.text
.L13:
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	orl	$1, %eax
	movl	%eax, %edx
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rcx
	movq	-16(%rbp), %rax
	addq	%rax, %rcx
	leaq	kabe(%rip), %rax
	addq	%rcx, %rax
	movb	%dl, (%rax)
	jmp	.L6
.L12:
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	orl	$2, %eax
	movl	%eax, %edx
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rcx
	movq	-16(%rbp), %rax
	addq	%rax, %rcx
	leaq	kabe(%rip), %rax
	addq	%rcx, %rax
	movb	%dl, (%rax)
	jmp	.L6
.L11:
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	orl	$4, %eax
	movl	%eax, %edx
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rcx
	movq	-16(%rbp), %rax
	addq	%rax, %rcx
	leaq	kabe(%rip), %rax
	addq	%rcx, %rax
	movb	%dl, (%rax)
	jmp	.L6
.L10:
	movq	-16(%rbp), %rax
	leaq	-1(%rax), %rdx
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movq	-16(%rbp), %rdx
	leaq	-1(%rdx), %rcx
	orl	$1, %eax
	movl	%eax, %edx
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rax
	addq	%rax, %rcx
	leaq	kabe(%rip), %rax
	addq	%rcx, %rax
	movb	%dl, (%rax)
	jmp	.L6
.L9:
	movq	-24(%rbp), %rax
	leaq	-1(%rax), %rdx
	movq	-16(%rbp), %rax
	leaq	-1(%rax), %rcx
	imulq	$2000, %rdx, %rax
	leaq	(%rax,%rcx), %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movq	-24(%rbp), %rdx
	leaq	-1(%rdx), %rcx
	movq	-16(%rbp), %rdx
	leaq	-1(%rdx), %rsi
	orl	$4, %eax
	movl	%eax, %edx
	imulq	$2000, %rcx, %rax
	leaq	(%rax,%rsi), %rcx
	leaq	kabe(%rip), %rax
	addq	%rcx, %rax
	movb	%dl, (%rax)
	jmp	.L6
.L7:
	movq	-24(%rbp), %rax
	addq	$1, %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movq	-24(%rbp), %rdx
	leaq	1(%rdx), %rcx
	orl	$2, %eax
	movl	%eax, %edx
	imulq	$2000, %rcx, %rcx
	movq	-16(%rbp), %rax
	addq	%rax, %rcx
	leaq	kabe(%rip), %rax
	addq	%rcx, %rax
	movb	%dl, (%rax)
	nop
.L6:
	movl	-40(%rbp), %eax
	cltq
	salq	$4, %rax
	movq	%rax, %rdx
	leaq	dputtern.0(%rip), %rax
	movq	(%rdx,%rax), %rax
	addq	%rax, -24(%rbp)
	movl	-40(%rbp), %eax
	cltq
	salq	$4, %rax
	movq	%rax, %rdx
	leaq	8+dputtern.0(%rip), %rax
	movq	(%rdx,%rax), %rax
	addq	%rax, -16(%rbp)
	addq	$1, -8(%rbp)
	movl	$1, -36(%rbp)
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movsbl	%al, %eax
	andl	$1, %eax
	testl	%eax, %eax
	jne	.L14
	movq	-16(%rbp), %rax
	leaq	-1(%rax), %rdx
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movsbl	%al, %eax
	andl	$1, %eax
	testl	%eax, %eax
	je	.L15
.L14:
	movl	$0, -36(%rbp)
	cmpl	$5, -40(%rbp)
	ja	.L15
	movl	-40(%rbp), %eax
	leaq	0(,%rax,4), %rdx
	leaq	.L17(%rip), %rax
	movl	(%rdx,%rax), %eax
	cltq
	leaq	.L17(%rip), %rdx
	addq	%rdx, %rax
	notrack jmp	*%rax
	.section	.rodata
	.align 4
	.align 4
.L17:
	.long	.L22-.L17
	.long	.L21-.L17
	.long	.L20-.L17
	.long	.L19-.L17
	.long	.L18-.L17
	.long	.L16-.L17
	.text
.L22:
	movl	$1, -36(%rbp)
	jmp	.L15
.L21:
	movl	$2, -40(%rbp)
	jmp	.L15
.L20:
	movl	$1, -40(%rbp)
	jmp	.L15
.L19:
	movl	$1, -36(%rbp)
	jmp	.L15
.L18:
	movl	$5, -40(%rbp)
	jmp	.L15
.L16:
	movl	$4, -40(%rbp)
	nop
.L15:
	cmpl	$0, -36(%rbp)
	je	.L23
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movsbl	%al, %eax
	andl	$2, %eax
	testl	%eax, %eax
	jne	.L24
	movq	-24(%rbp), %rax
	addq	$1, %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movsbl	%al, %eax
	andl	$2, %eax
	testl	%eax, %eax
	je	.L23
.L24:
	movl	$0, -36(%rbp)
	cmpl	$5, -40(%rbp)
	ja	.L23
	movl	-40(%rbp), %eax
	leaq	0(,%rax,4), %rdx
	leaq	.L26(%rip), %rax
	movl	(%rdx,%rax), %eax
	cltq
	leaq	.L26(%rip), %rdx
	addq	%rdx, %rax
	notrack jmp	*%rax
	.section	.rodata
	.align 4
	.align 4
.L26:
	.long	.L31-.L26
	.long	.L30-.L26
	.long	.L29-.L26
	.long	.L28-.L26
	.long	.L27-.L26
	.long	.L25-.L26
	.text
.L31:
	movl	$4, -40(%rbp)
	jmp	.L23
.L30:
	movl	$1, -36(%rbp)
	jmp	.L23
.L29:
	movl	$3, -40(%rbp)
	jmp	.L23
.L28:
	movl	$2, -40(%rbp)
	jmp	.L23
.L27:
	movl	$0, -40(%rbp)
	jmp	.L23
.L25:
	movl	$1, -36(%rbp)
	nop
.L23:
	cmpl	$0, -36(%rbp)
	je	.L32
	movq	-24(%rbp), %rax
	imulq	$2000, %rax, %rdx
	movq	-16(%rbp), %rax
	addq	%rax, %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movsbl	%al, %eax
	andl	$4, %eax
	testl	%eax, %eax
	jne	.L33
	movq	-24(%rbp), %rax
	leaq	-1(%rax), %rdx
	movq	-16(%rbp), %rax
	leaq	-1(%rax), %rcx
	imulq	$2000, %rdx, %rax
	leaq	(%rax,%rcx), %rdx
	leaq	kabe(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	movsbl	%al, %eax
	andl	$4, %eax
	testl	%eax, %eax
	je	.L32
.L33:
	cmpl	$5, -40(%rbp)
	ja	.L32
	movl	-40(%rbp), %eax
	leaq	0(,%rax,4), %rdx
	leaq	.L35(%rip), %rax
	movl	(%rdx,%rax), %eax
	cltq
	leaq	.L35(%rip), %rdx
	addq	%rdx, %rax
	notrack jmp	*%rax
	.section	.rodata
	.align 4
	.align 4
.L35:
	.long	.L40-.L35
	.long	.L39-.L35
	.long	.L38-.L35
	.long	.L37-.L35
	.long	.L36-.L35
	.long	.L34-.L35
	.text
.L40:
	movl	$5, -40(%rbp)
	jmp	.L32
.L39:
	movl	$3, -40(%rbp)
	jmp	.L32
.L38:
	movl	$1, -36(%rbp)
	jmp	.L32
.L37:
	movl	$1, -40(%rbp)
	jmp	.L32
.L36:
	movl	$1, -36(%rbp)
	jmp	.L32
.L34:
	movl	$0, -40(%rbp)
	nop
.L32:
	cmpq	$0, -8(%rbp)
	je	.L41
	movq	-64(%rbp), %rax
	addq	$10, %rax
	cmpq	%rax, -24(%rbp)
	jne	.L41
	cmpq	$10, -16(%rbp)
	jne	.L41
	movq	-8(%rbp), %rax
	jmp	.L42
.L2:
	movq	-56(%rbp), %rdx
	movq	%rdx, %rax
	addq	%rax, %rax
	addq	%rdx, %rax
	subq	$3, %rax
.L42:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE0:
	.size	solve, .-solve
	.globl	gcd
	.type	gcd, @function
gcd:
.LFB1:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movq	%rdi, -24(%rbp)
	movq	%rsi, -32(%rbp)
	jmp	.L44
.L45:
	movq	-24(%rbp), %rax
	movl	$0, %edx
	divq	-32(%rbp)
	movq	%rdx, -8(%rbp)
	movq	-32(%rbp), %rax
	movq	%rax, -24(%rbp)
	movq	-8(%rbp), %rax
	movq	%rax, -32(%rbp)
.L44:
	cmpq	$0, -32(%rbp)
	jne	.L45
	movq	-24(%rbp), %rax
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE1:
	.size	gcd, .-gcd
	.section	.rodata
.LC0:
	.string	"%lu%lu"
.LC1:
	.string	"%lu\n"
	.text
	.globl	main
	.type	main, @function
main:
.LFB2:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	pushq	%rbx
	subq	$40, %rsp
	.cfi_offset 3, -24
	movq	%fs:40, %rax
	movq	%rax, -24(%rbp)
	xorl	%eax, %eax
	leaq	-32(%rbp), %rdx
	leaq	-40(%rbp), %rax
	movq	%rax, %rsi
	leaq	.LC0(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	cmpl	$2, %eax
	je	.L48
	movl	$1, %eax
	jmp	.L50
.L48:
	movq	-40(%rbp), %rbx
	movq	-32(%rbp), %rdx
	movq	-40(%rbp), %rax
	movq	%rdx, %rsi
	movq	%rax, %rdi
	call	gcd
	subq	%rax, %rbx
	movq	%rbx, %rdx
	movq	%rdx, %rax
	addq	%rax, %rax
	addq	%rdx, %rax
	movq	%rax, %rsi
	leaq	.LC1(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
	movl	$0, %eax
.L50:
	movq	-24(%rbp), %rdx
	subq	%fs:40, %rdx
	je	.L51
	call	__stack_chk_fail@PLT
.L51:
	movq	-8(%rbp), %rbx
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE2:
	.size	main, .-main
	.section	.rodata
	.align 32
	.type	dputtern.0, @object
	.size	dputtern.0, 96
dputtern.0:
	.quad	0
	.quad	1
	.quad	-1
	.quad	0
	.quad	1
	.quad	1
	.quad	0
	.quad	-1
	.quad	-1
	.quad	-1
	.quad	1
	.quad	0
	.ident	"GCC: (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:
