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

```c
// Aizu 1163: Cards
// 2017.9.15 bal4u@uu

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

#define M 502
#define N 502

int m, n;
char graph[M][N], seen[N];
int matchL[M], matchR[N];

int b[M], r[N];

int gcd(int a, int b)
{
	int r;
	while (b != 0) r = a % b, a = b, b = r;
	return a;
}

int bpm(int u)
{
	int v;

	for (v = 0; v < n; v++) if (graph[u][v]) {
		if (seen[v]) continue;
		seen[v] = 1;
		if (matchR[v] < 0 || bpm(matchR[v])) {
			matchL[u] = v, matchR[v] = u;
			return 1;
		}
	}
	return 0;
}

int main()
{
	int i, j, cnt;

	while (scanf("%d%d", &m, &n) && m) {
		for (i = 0; i < m; i++) scanf("%d", b+i);
		for (j = 0; j < n; j++) scanf("%d", r+j);
	    for (i = 0; i < m; i++) for (j = 0; j < n; j++) graph[i][j] = (gcd(b[i], r[j]) > 1);
		memset(matchL, -1, m*sizeof(matchL[0]));
		memset(matchR, -1, n*sizeof(matchR[0]));
		for (cnt = 0, i = 0; i < m; i++) { memset(seen, 0, n); if (bpm(i)) cnt++; }
		printf("%d\n", cnt);
	}
	return 0;
}```

Unoptimized Assembly Code:

```assembly
	.file	"temp.c"
	.text
	.globl	m
	.bss
	.align 4
	.type	m, @object
	.size	m, 4
m:
	.zero	4
	.globl	n
	.align 4
	.type	n, @object
	.size	n, 4
n:
	.zero	4
	.globl	graph
	.align 32
	.type	graph, @object
	.size	graph, 252004
graph:
	.zero	252004
	.globl	seen
	.align 32
	.type	seen, @object
	.size	seen, 502
seen:
	.zero	502
	.globl	matchL
	.align 32
	.type	matchL, @object
	.size	matchL, 2008
matchL:
	.zero	2008
	.globl	matchR
	.align 32
	.type	matchR, @object
	.size	matchR, 2008
matchR:
	.zero	2008
	.globl	b
	.align 32
	.type	b, @object
	.size	b, 2008
b:
	.zero	2008
	.globl	r
	.align 32
	.type	r, @object
	.size	r, 2008
r:
	.zero	2008
	.text
	.globl	gcd
	.type	gcd, @function
gcd:
.LFB0:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movl	%edi, -20(%rbp)
	movl	%esi, -24(%rbp)
	jmp	.L2
.L3:
	movl	-20(%rbp), %eax
	cltd
	idivl	-24(%rbp)
	movl	%edx, -4(%rbp)
	movl	-24(%rbp), %eax
	movl	%eax, -20(%rbp)
	movl	-4(%rbp), %eax
	movl	%eax, -24(%rbp)
.L2:
	cmpl	$0, -24(%rbp)
	jne	.L3
	movl	-20(%rbp), %eax
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE0:
	.size	gcd, .-gcd
	.globl	bpm
	.type	bpm, @function
bpm:
.LFB1:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$32, %rsp
	movl	%edi, -20(%rbp)
	movl	$0, -4(%rbp)
	jmp	.L6
.L11:
	movl	-4(%rbp), %eax
	movslq	%eax, %rdx
	movl	-20(%rbp), %eax
	cltq
	imulq	$502, %rax, %rax
	addq	%rax, %rdx
	leaq	graph(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	testb	%al, %al
	je	.L7
	movl	-4(%rbp), %eax
	cltq
	leaq	seen(%rip), %rdx
	movzbl	(%rax,%rdx), %eax
	testb	%al, %al
	jne	.L12
	movl	-4(%rbp), %eax
	cltq
	leaq	seen(%rip), %rdx
	movb	$1, (%rax,%rdx)
	movl	-4(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	matchR(%rip), %rax
	movl	(%rdx,%rax), %eax
	testl	%eax, %eax
	js	.L9
	movl	-4(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	matchR(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, %edi
	call	bpm
	testl	%eax, %eax
	je	.L7
.L9:
	movl	-20(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rcx
	leaq	matchL(%rip), %rdx
	movl	-4(%rbp), %eax
	movl	%eax, (%rcx,%rdx)
	movl	-4(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rcx
	leaq	matchR(%rip), %rdx
	movl	-20(%rbp), %eax
	movl	%eax, (%rcx,%rdx)
	movl	$1, %eax
	jmp	.L10
.L12:
	nop
.L7:
	addl	$1, -4(%rbp)
.L6:
	movl	n(%rip), %eax
	cmpl	%eax, -4(%rbp)
	jl	.L11
	movl	$0, %eax
.L10:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE1:
	.size	bpm, .-bpm
	.section	.rodata
.LC0:
	.string	"%d"
.LC1:
	.string	"%d\n"
.LC2:
	.string	"%d%d"
	.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
	subq	$16, %rsp
	jmp	.L14
.L27:
	movl	$0, -12(%rbp)
	jmp	.L15
.L16:
	movl	-12(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	b(%rip), %rax
	addq	%rdx, %rax
	movq	%rax, %rsi
	leaq	.LC0(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	addl	$1, -12(%rbp)
.L15:
	movl	m(%rip), %eax
	cmpl	%eax, -12(%rbp)
	jl	.L16
	movl	$0, -8(%rbp)
	jmp	.L17
.L18:
	movl	-8(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	r(%rip), %rax
	addq	%rdx, %rax
	movq	%rax, %rsi
	leaq	.LC0(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	addl	$1, -8(%rbp)
.L17:
	movl	n(%rip), %eax
	cmpl	%eax, -8(%rbp)
	jl	.L18
	movl	$0, -12(%rbp)
	jmp	.L19
.L22:
	movl	$0, -8(%rbp)
	jmp	.L20
.L21:
	movl	-8(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	r(%rip), %rax
	movl	(%rdx,%rax), %edx
	movl	-12(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rcx
	leaq	b(%rip), %rax
	movl	(%rcx,%rax), %eax
	movl	%edx, %esi
	movl	%eax, %edi
	call	gcd
	cmpl	$1, %eax
	setg	%al
	movl	%eax, %edx
	movl	-8(%rbp), %eax
	movslq	%eax, %rcx
	movl	-12(%rbp), %eax
	cltq
	imulq	$502, %rax, %rax
	addq	%rax, %rcx
	leaq	graph(%rip), %rax
	addq	%rcx, %rax
	movb	%dl, (%rax)
	addl	$1, -8(%rbp)
.L20:
	movl	n(%rip), %eax
	cmpl	%eax, -8(%rbp)
	jl	.L21
	addl	$1, -12(%rbp)
.L19:
	movl	m(%rip), %eax
	cmpl	%eax, -12(%rbp)
	jl	.L22
	movl	m(%rip), %eax
	cltq
	salq	$2, %rax
	movq	%rax, %rdx
	movl	$-1, %esi
	leaq	matchL(%rip), %rax
	movq	%rax, %rdi
	call	memset@PLT
	movl	n(%rip), %eax
	cltq
	salq	$2, %rax
	movq	%rax, %rdx
	movl	$-1, %esi
	leaq	matchR(%rip), %rax
	movq	%rax, %rdi
	call	memset@PLT
	movl	$0, -4(%rbp)
	movl	$0, -12(%rbp)
	jmp	.L23
.L25:
	movl	n(%rip), %eax
	cltq
	movq	%rax, %rdx
	movl	$0, %esi
	leaq	seen(%rip), %rax
	movq	%rax, %rdi
	call	memset@PLT
	movl	-12(%rbp), %eax
	movl	%eax, %edi
	call	bpm
	testl	%eax, %eax
	je	.L24
	addl	$1, -4(%rbp)
.L24:
	addl	$1, -12(%rbp)
.L23:
	movl	m(%rip), %eax
	cmpl	%eax, -12(%rbp)
	jl	.L25
	movl	-4(%rbp), %eax
	movl	%eax, %esi
	leaq	.LC1(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
.L14:
	leaq	n(%rip), %rax
	movq	%rax, %rdx
	leaq	m(%rip), %rax
	movq	%rax, %rsi
	leaq	.LC2(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	testl	%eax, %eax
	je	.L26
	movl	m(%rip), %eax
	testl	%eax, %eax
	jne	.L27
.L26:
	movl	$0, %eax
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE2:
	.size	main, .-main
	.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	gcd
	.type	gcd, @function
gcd:
.LFB35:
	.cfi_startproc
	endbr64
	movl	%edi, %eax
	movl	%esi, %edx
	testl	%esi, %esi
	je	.L4
	.p2align 4,,10
	.p2align 3
.L3:
	movl	%edx, %r8d
	cltd
	idivl	%r8d
	movl	%r8d, %eax
	testl	%edx, %edx
	jne	.L3
	movl	%r8d, %eax
	ret
	.p2align 4,,10
	.p2align 3
.L4:
	movl	%edi, %r8d
	movl	%r8d, %eax
	ret
	.cfi_endproc
.LFE35:
	.size	gcd, .-gcd
	.p2align 4
	.globl	bpm
	.type	bpm, @function
bpm:
.LFB36:
	.cfi_startproc
	endbr64
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	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
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	subq	$264, %rsp
	.cfi_def_cfa_offset 320
	movl	n(%rip), %eax
	movl	%edi, 176(%rsp)
	testl	%eax, %eax
	jle	.L37
	movslq	176(%rsp), %rdx
	leaq	graph(%rip), %rsi
	movq	$0, 144(%rsp)
	leaq	matchR(%rip), %r11
	movq	%rdx, 224(%rsp)
	imulq	$502, %rdx, %rdx
	addq	%rsi, %rdx
	movq	%rdx, 192(%rsp)
	leaq	seen(%rip), %rdx
.L36:
	movq	144(%rsp), %rsi
	movq	192(%rsp), %rcx
	cmpb	$0, (%rcx,%rsi)
	movl	%esi, 180(%rsp)
	je	.L10
	cmpb	$0, (%rdx,%rsi)
	jne	.L10
	movb	$1, (%rdx,%rsi)
	movl	(%r11,%rsi,4), %esi
	movl	%esi, 164(%rsp)
	testl	%esi, %esi
	js	.L64
	movslq	164(%rsp), %rdi
	leaq	graph(%rip), %rsi
	movq	$0, 136(%rsp)
	imulq	$502, %rdi, %rcx
	movq	%rdi, 200(%rsp)
	leaq	(%rsi,%rcx), %rdi
	movq	%rdi, 184(%rsp)
.L35:
	movq	136(%rsp), %rdi
	movq	184(%rsp), %rcx
	cmpb	$0, (%rcx,%rdi)
	movl	%edi, 232(%rsp)
	je	.L12
	cmpb	$0, (%rdx,%rdi)
	jne	.L12
	movl	(%r11,%rdi,4), %ecx
	movb	$1, (%rdx,%rdi)
	movl	%ecx, 168(%rsp)
	testl	%ecx, %ecx
	js	.L65
	movslq	168(%rsp), %rsi
	leaq	graph(%rip), %rdi
	movq	$0, 88(%rsp)
	imulq	$502, %rsi, %rcx
	movq	%rsi, 208(%rsp)
	leaq	(%rdi,%rcx), %rsi
	movq	%rsi, 128(%rsp)
.L34:
	movq	88(%rsp), %rsi
	movq	128(%rsp), %rcx
	cmpb	$0, (%rcx,%rsi)
	movl	%esi, 160(%rsp)
	je	.L14
	cmpb	$0, (%rdx,%rsi)
	jne	.L14
	movl	(%r11,%rsi,4), %edi
	movb	$1, (%rdx,%rsi)
	movl	%edi, 172(%rsp)
	testl	%edi, %edi
	js	.L66
	movslq	172(%rsp), %rcx
	leaq	graph(%rip), %rdi
	movq	$0, 40(%rsp)
	movq	%rcx, 216(%rsp)
	imulq	$502, %rcx, %rcx
	leaq	(%rdi,%rcx), %rsi
	movq	%rsi, 96(%rsp)
	.p2align 4,,10
	.p2align 3
.L33:
	movq	40(%rsp), %rsi
	movq	96(%rsp), %rdi
	cmpb	$0, (%rdi,%rsi)
	movl	%esi, 120(%rsp)
	je	.L16
	cmpb	$0, (%rdx,%rsi)
	jne	.L16
	movb	$1, (%rdx,%rsi)
	movl	(%r11,%rsi,4), %esi
	movl	%esi, 124(%rsp)
	testl	%esi, %esi
	js	.L67
	movslq	124(%rsp), %rcx
	leaq	graph(%rip), %rsi
	movq	%rcx, 152(%rsp)
	imulq	$502, %rcx, %rcx
	addq	%rsi, %rcx
	xorl	%esi, %esi
	movq	%rcx, 48(%rsp)
	.p2align 4,,10
	.p2align 3
.L32:
	movq	48(%rsp), %rdi
	movl	%esi, 80(%rsp)
	cmpb	$0, (%rdi,%rsi)
	je	.L18
	cmpb	$0, (%rdx,%rsi)
	jne	.L18
	movl	(%r11,%rsi,4), %ecx
	movb	$1, (%rdx,%rsi)
	movl	%ecx, 84(%rsp)
	testl	%ecx, %ecx
	js	.L68
	movslq	84(%rsp), %rcx
	leaq	graph(%rip), %rdi
	movq	%rsi, 104(%rsp)
	xorl	%r12d, %r12d
	movq	%rcx, 112(%rsp)
	imulq	$502, %rcx, %rcx
	addq	%rcx, %rdi
	movq	%rdi, 8(%rsp)
	.p2align 4,,10
	.p2align 3
.L31:
	movq	8(%rsp), %rdi
	movl	%r12d, 20(%rsp)
	cmpb	$0, (%rdi,%r12)
	je	.L20
	cmpb	$0, (%rdx,%r12)
	jne	.L20
	movl	(%r11,%r12,4), %edi
	movb	$1, (%rdx,%r12)
	movl	%edi, 36(%rsp)
	testl	%edi, %edi
	js	.L69
	movslq	36(%rsp), %rcx
	movq	%r12, 56(%rsp)
	leaq	graph(%rip), %rdi
	xorl	%ebp, %ebp
	imulq	$502, %rcx, %r15
	movq	%rcx, 64(%rsp)
	addq	%rdi, %r15
	.p2align 4,,10
	.p2align 3
.L30:
	cmpb	$0, (%r15,%rbp)
	movl	%ebp, 32(%rsp)
	je	.L22
	cmpb	$0, (%rdx,%rbp)
	jne	.L22
	movl	(%r11,%rbp,4), %r10d
	movb	$1, (%rdx,%rbp)
	testl	%r10d, %r10d
	js	.L70
	movslq	%r10d, %r8
	leaq	graph(%rip), %rdi
	xorl	%ebx, %ebx
	imulq	$502, %r8, %r14
	addq	%rdi, %r14
	.p2align 4,,10
	.p2align 3
.L29:
	cmpb	$0, (%r14,%rbx)
	movl	%ebx, %ecx
	je	.L24
	cmpb	$0, (%rdx,%rbx)
	jne	.L24
	movl	(%r11,%rbx,4), %r9d
	movb	$1, (%rdx,%rbx)
	testl	%r9d, %r9d
	js	.L71
	movslq	%r9d, %rdi
	xorl	%r13d, %r13d
	imulq	$502, %rdi, %rsi
	movq	%rdi, 24(%rsp)
	leaq	graph(%rip), %rdi
	addq	%rdi, %rsi
	.p2align 4,,10
	.p2align 3
.L28:
	cmpb	$0, (%rsi,%r13)
	movl	%r13d, %r12d
	je	.L26
	cmpb	$0, (%rdx,%r13)
	jne	.L26
	movl	(%r11,%r13,4), %edi
	movq	%rsi, 72(%rsp)
	movb	$1, (%rdx,%r13)
	testl	%edi, %edi
	js	.L27
	movq	%r8, 248(%rsp)
	movl	%ecx, 244(%rsp)
	movl	%r9d, 240(%rsp)
	movl	%r10d, 236(%rsp)
	call	bpm
	movl	236(%rsp), %r10d
	movl	240(%rsp), %r9d
	leaq	matchR(%rip), %r11
	testl	%eax, %eax
	movl	244(%rsp), %ecx
	movq	248(%rsp), %r8
	jne	.L27
	movl	n(%rip), %eax
	movq	72(%rsp), %rsi
	leaq	seen(%rip), %rdx
	.p2align 4,,10
	.p2align 3
.L26:
	addq	$1, %r13
	cmpl	%r13d, %eax
	jg	.L28
.L24:
	addq	$1, %rbx
	cmpl	%ebx, %eax
	jg	.L29
.L22:
	addq	$1, %rbp
	cmpl	%ebp, %eax
	jg	.L30
	movq	56(%rsp), %r12
.L20:
	addq	$1, %r12
	cmpl	%r12d, %eax
	jg	.L31
	movq	104(%rsp), %rsi
.L18:
	addq	$1, %rsi
	cmpl	%esi, %eax
	jg	.L32
.L16:
	addq	$1, 40(%rsp)
	movq	40(%rsp), %rsi
	cmpl	%esi, %eax
	jg	.L33
.L14:
	addq	$1, 88(%rsp)
	movq	88(%rsp), %rsi
	cmpl	%esi, %eax
	jg	.L34
.L12:
	addq	$1, 136(%rsp)
	movq	136(%rsp), %rdi
	cmpl	%edi, %eax
	jg	.L35
.L10:
	addq	$1, 144(%rsp)
	movq	144(%rsp), %rcx
	cmpl	%ecx, %eax
	jg	.L36
.L37:
	xorl	%eax, %eax
.L7:
	addq	$264, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 56
	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
.L27:
	.cfi_restore_state
	movq	24(%rsp), %rax
	leaq	matchL(%rip), %rdx
	movq	%r8, %rsi
	movl	%r9d, %r8d
	movl	%r10d, %r9d
	movl	%ecx, %r10d
	movl	%r12d, (%rdx,%rax,4)
	movslq	%r12d, %rax
	movl	%r8d, (%r11,%rax,4)
.L25:
	movslq	%r10d, %rax
	movl	%r10d, (%rdx,%rsi,4)
	movl	%r9d, (%r11,%rax,4)
.L23:
	movq	64(%rsp), %rsi
	movslq	32(%rsp), %rax
	movl	%eax, (%rdx,%rsi,4)
	movl	36(%rsp), %esi
	movl	%esi, (%r11,%rax,4)
.L21:
	movslq	20(%rsp), %rax
	movq	112(%rsp), %rcx
	movl	84(%rsp), %esi
	movl	%eax, (%rdx,%rcx,4)
	movl	%esi, (%r11,%rax,4)
.L19:
	movslq	80(%rsp), %rax
	movq	152(%rsp), %rcx
	movl	124(%rsp), %esi
	movl	%eax, (%rdx,%rcx,4)
	movl	%esi, (%r11,%rax,4)
.L17:
	movslq	120(%rsp), %rax
	movq	216(%rsp), %rdi
	movl	172(%rsp), %ecx
	movl	%eax, (%rdx,%rdi,4)
	movl	%ecx, (%r11,%rax,4)
.L15:
	movslq	160(%rsp), %rax
	movq	208(%rsp), %rsi
	movl	168(%rsp), %edi
	movl	%eax, (%rdx,%rsi,4)
	movl	%edi, (%r11,%rax,4)
.L13:
	movslq	232(%rsp), %rax
	movq	200(%rsp), %rcx
	movl	164(%rsp), %esi
	movl	%eax, (%rdx,%rcx,4)
	movl	%esi, (%r11,%rax,4)
.L11:
	movslq	180(%rsp), %rax
	movq	224(%rsp), %rdi
	movl	%eax, (%rdx,%rdi,4)
	movl	176(%rsp), %edx
	movl	%edx, (%r11,%rax,4)
	movl	$1, %eax
	jmp	.L7
	.p2align 4,,10
	.p2align 3
.L71:
	movl	%r10d, %r9d
	movq	%r8, %rsi
	leaq	matchL(%rip), %rdx
	movl	%ebx, %r10d
	jmp	.L25
.L70:
	leaq	matchL(%rip), %rdx
	jmp	.L23
.L69:
	leaq	matchL(%rip), %rdx
	jmp	.L21
.L68:
	leaq	matchL(%rip), %rdx
	jmp	.L19
.L67:
	leaq	matchL(%rip), %rdx
	jmp	.L17
.L66:
	leaq	matchL(%rip), %rdx
	jmp	.L15
.L65:
	leaq	matchL(%rip), %rdx
	jmp	.L13
.L64:
	leaq	matchL(%rip), %rdx
	jmp	.L11
	.cfi_endproc
.LFE36:
	.size	bpm, .-bpm
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC0:
	.string	"%d"
.LC1:
	.string	"%d\n"
.LC2:
	.string	"%d%d"
	.section	.text.startup,"ax",@progbits
	.p2align 4
	.globl	main
	.type	main, @function
main:
.LFB37:
	.cfi_startproc
	endbr64
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	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
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	leaq	matchR(%rip), %rbp
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	leaq	seen(%rip), %rbx
	subq	$40, %rsp
	.cfi_def_cfa_offset 96
.L73:
	xorl	%eax, %eax
	leaq	n(%rip), %rdx
	leaq	m(%rip), %rsi
	leaq	.LC2(%rip), %rdi
	call	__isoc99_scanf@PLT
	testl	%eax, %eax
	je	.L99
	movl	m(%rip), %r14d
	testl	%r14d, %r14d
	je	.L99
	leaq	b(%rip), %r13
	movl	$0, %r12d
	jle	.L92
	.p2align 4,,10
	.p2align 3
.L74:
	movq	%r13, %rsi
	leaq	.LC0(%rip), %rdi
	xorl	%eax, %eax
	addl	$1, %r12d
	call	__isoc99_scanf@PLT
	movl	m(%rip), %r14d
	addq	$4, %r13
	cmpl	%r12d, %r14d
	jg	.L74
.L92:
	movslq	n(%rip), %rax
	testl	%eax, %eax
	jle	.L75
	leaq	r(%rip), %r12
	xorl	%r13d, %r13d
	movq	%r12, %r14
	.p2align 4,,10
	.p2align 3
.L76:
	movq	%r14, %rsi
	leaq	.LC0(%rip), %rdi
	xorl	%eax, %eax
	addl	$1, %r13d
	call	__isoc99_scanf@PLT
	movl	n(%rip), %eax
	addq	$4, %r14
	cmpl	%r13d, %eax
	jg	.L76
	movslq	m(%rip), %r13
	movslq	%eax, %r10
	leaq	0(,%r10,4), %rdi
	movq	%r13, %r14
	movq	%rdi, 8(%rsp)
	salq	$2, %r13
	testl	%r14d, %r14d
	jle	.L77
	testl	%eax, %eax
	jle	.L78
	leaq	b(%rip), %r11
	leal	-1(%r14), %eax
	leaq	4(%r11), %rdx
	leaq	graph(%rip), %rdi
	leaq	(%rdx,%rax,4), %r8
	.p2align 4,,10
	.p2align 3
.L79:
	movl	(%r11), %r9d
	xorl	%esi, %esi
	.p2align 4,,10
	.p2align 3
.L82:
	movl	(%r12,%rsi,4), %edx
	testl	%edx, %edx
	je	.L96
	movl	%r9d, %eax
	.p2align 4,,10
	.p2align 3
.L81:
	movl	%edx, %ecx
	cltd
	idivl	%ecx
	movl	%ecx, %eax
	testl	%edx, %edx
	jne	.L81
	cmpl	$1, %ecx
	setg	(%rdi,%rsi)
	addq	$1, %rsi
	cmpq	%r10, %rsi
	jne	.L82
.L118:
	addq	$4, %r11
	addq	$502, %rdi
	cmpq	%r8, %r11
	jne	.L79
.L78:
	movq	%r13, %rdx
	movl	$2008, %ecx
	movl	$-1, %esi
	xorl	%r15d, %r15d
	leaq	matchL(%rip), %rdi
	leaq	graph(%rip), %r13
	call	__memset_chk@PLT
	movq	8(%rsp), %rdx
	movl	$2008, %ecx
	movq	%rbp, %rdi
	movl	$-1, %esi
	call	__memset_chk@PLT
	leaq	matchL(%rip), %rax
	movl	$0, 28(%rsp)
	movq	%rax, 16(%rsp)
	.p2align 4,,10
	.p2align 3
.L94:
	movslq	n(%rip), %rdx
	movl	$502, %ecx
	xorl	%esi, %esi
	movq	%rbx, %rdi
	movl	%edx, 8(%rsp)
	call	__memset_chk@PLT
	movl	8(%rsp), %r8d
	testl	%r8d, %r8d
	jle	.L85
	xorl	%r14d, %r14d
	.p2align 4,,10
	.p2align 3
.L89:
	cmpb	$0, 0(%r13,%r14)
	movl	%r14d, %r12d
	je	.L86
	cmpb	$0, (%rbx,%r14)
	jne	.L86
	movl	0(%rbp,%r14,4), %edi
	movb	$1, (%rbx,%r14)
	testl	%edi, %edi
	js	.L87
	call	bpm
	testl	%eax, %eax
	jne	.L87
	movl	n(%rip), %r8d
.L86:
	addq	$1, %r14
	cmpl	%r14d, %r8d
	jg	.L89
	movl	%r15d, %eax
	movl	m(%rip), %r14d
	addl	$1, %eax
	movl	%eax, %r15d
	cmpl	%eax, %r14d
	jle	.L93
.L95:
	addq	$4, 16(%rsp)
	addq	$502, %r13
	jmp	.L94
	.p2align 4,,10
	.p2align 3
.L96:
	movl	%r9d, %ecx
	cmpl	$1, %ecx
	setg	(%rdi,%rsi)
	addq	$1, %rsi
	cmpq	%r10, %rsi
	jne	.L82
	jmp	.L118
.L87:
	movq	16(%rsp), %rax
	movl	m(%rip), %r14d
	movslq	%r12d, %rdx
	movl	%r15d, 0(%rbp,%rdx,4)
	movl	%r12d, (%rax)
	movl	%r15d, %eax
	addl	$1, %eax
	addl	$1, 28(%rsp)
	movl	%eax, %r15d
	cmpl	%eax, %r14d
	jg	.L95
.L93:
	movl	28(%rsp), %edx
	leaq	.LC1(%rip), %rsi
	movl	$1, %edi
	xorl	%eax, %eax
	call	__printf_chk@PLT
	jmp	.L73
.L75:
	movslq	%r14d, %r13
	salq	$2, %rax
	movq	%rax, 8(%rsp)
	salq	$2, %r13
	testl	%r14d, %r14d
	jg	.L78
.L77:
	movl	$2008, %ecx
	movq	%r13, %rdx
	movl	$-1, %esi
	leaq	matchL(%rip), %rdi
	call	__memset_chk@PLT
	movq	8(%rsp), %rdx
	movl	$2008, %ecx
	movq	%rbp, %rdi
	movl	$-1, %esi
	call	__memset_chk@PLT
	movl	$0, 28(%rsp)
	jmp	.L93
.L99:
	addq	$40, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 56
	xorl	%eax, %eax
	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
.L85:
	.cfi_restore_state
	movl	%r15d, %r12d
	addl	$1, %r12d
	cmpl	%r14d, %r12d
	jge	.L93
	.p2align 4,,10
	.p2align 3
.L83:
	movslq	n(%rip), %rdx
	xorl	%esi, %esi
	movq	%rbx, %rdi
	addl	$1, %r12d
	movl	$502, %ecx
	call	__memset_chk@PLT
	cmpl	%r14d, %r12d
	jl	.L83
	jmp	.L93
	.cfi_endproc
.LFE37:
	.size	main, .-main
	.globl	r
	.bss
	.align 32
	.type	r, @object
	.size	r, 2008
r:
	.zero	2008
	.globl	b
	.align 32
	.type	b, @object
	.size	b, 2008
b:
	.zero	2008
	.globl	matchR
	.align 32
	.type	matchR, @object
	.size	matchR, 2008
matchR:
	.zero	2008
	.globl	matchL
	.align 32
	.type	matchL, @object
	.size	matchL, 2008
matchL:
	.zero	2008
	.globl	seen
	.align 32
	.type	seen, @object
	.size	seen, 502
seen:
	.zero	502
	.globl	graph
	.align 32
	.type	graph, @object
	.size	graph, 252004
graph:
	.zero	252004
	.globl	n
	.align 4
	.type	n, @object
	.size	n, 4
n:
	.zero	4
	.globl	m
	.align 4
	.type	m, @object
	.size	m, 4
m:
	.zero	4
	.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	gcd
	.type	gcd, @function
gcd:
.LFB35:
	.cfi_startproc
	endbr64
	movl	%edi, %eax
	movl	%esi, %edx
	testl	%esi, %esi
	je	.L4
	.p2align 4,,10
	.p2align 3
.L3:
	movl	%edx, %r8d
	cltd
	idivl	%r8d
	movl	%r8d, %eax
	testl	%edx, %edx
	jne	.L3
	movl	%r8d, %eax
	ret
	.p2align 4,,10
	.p2align 3
.L4:
	movl	%edi, %r8d
	movl	%r8d, %eax
	ret
	.cfi_endproc
.LFE35:
	.size	gcd, .-gcd
	.p2align 4
	.globl	bpm
	.type	bpm, @function
bpm:
.LFB36:
	.cfi_startproc
	endbr64
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	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
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	subq	$264, %rsp
	.cfi_def_cfa_offset 320
	movl	n(%rip), %eax
	movl	%edi, 176(%rsp)
	testl	%eax, %eax
	jle	.L37
	movslq	176(%rsp), %rdx
	leaq	graph(%rip), %rsi
	movq	$0, 144(%rsp)
	leaq	matchR(%rip), %r11
	movq	%rdx, 224(%rsp)
	imulq	$502, %rdx, %rdx
	addq	%rsi, %rdx
	movq	%rdx, 192(%rsp)
	leaq	seen(%rip), %rdx
.L36:
	movq	144(%rsp), %rsi
	movq	192(%rsp), %rcx
	cmpb	$0, (%rcx,%rsi)
	movl	%esi, 180(%rsp)
	je	.L10
	cmpb	$0, (%rdx,%rsi)
	jne	.L10
	movb	$1, (%rdx,%rsi)
	movl	(%r11,%rsi,4), %esi
	movl	%esi, 164(%rsp)
	testl	%esi, %esi
	js	.L64
	movslq	164(%rsp), %rdi
	leaq	graph(%rip), %rsi
	movq	$0, 136(%rsp)
	imulq	$502, %rdi, %rcx
	movq	%rdi, 200(%rsp)
	leaq	(%rsi,%rcx), %rdi
	movq	%rdi, 184(%rsp)
.L35:
	movq	136(%rsp), %rdi
	movq	184(%rsp), %rcx
	cmpb	$0, (%rcx,%rdi)
	movl	%edi, 232(%rsp)
	je	.L12
	cmpb	$0, (%rdx,%rdi)
	jne	.L12
	movl	(%r11,%rdi,4), %ecx
	movb	$1, (%rdx,%rdi)
	movl	%ecx, 168(%rsp)
	testl	%ecx, %ecx
	js	.L65
	movslq	168(%rsp), %rsi
	leaq	graph(%rip), %rdi
	movq	$0, 88(%rsp)
	imulq	$502, %rsi, %rcx
	movq	%rsi, 208(%rsp)
	leaq	(%rdi,%rcx), %rsi
	movq	%rsi, 128(%rsp)
.L34:
	movq	88(%rsp), %rsi
	movq	128(%rsp), %rcx
	cmpb	$0, (%rcx,%rsi)
	movl	%esi, 160(%rsp)
	je	.L14
	cmpb	$0, (%rdx,%rsi)
	jne	.L14
	movl	(%r11,%rsi,4), %edi
	movb	$1, (%rdx,%rsi)
	movl	%edi, 172(%rsp)
	testl	%edi, %edi
	js	.L66
	movslq	172(%rsp), %rcx
	leaq	graph(%rip), %rdi
	movq	$0, 40(%rsp)
	movq	%rcx, 216(%rsp)
	imulq	$502, %rcx, %rcx
	leaq	(%rdi,%rcx), %rsi
	movq	%rsi, 96(%rsp)
	.p2align 4,,10
	.p2align 3
.L33:
	movq	40(%rsp), %rsi
	movq	96(%rsp), %rdi
	cmpb	$0, (%rdi,%rsi)
	movl	%esi, 120(%rsp)
	je	.L16
	cmpb	$0, (%rdx,%rsi)
	jne	.L16
	movb	$1, (%rdx,%rsi)
	movl	(%r11,%rsi,4), %esi
	movl	%esi, 124(%rsp)
	testl	%esi, %esi
	js	.L67
	movslq	124(%rsp), %rcx
	leaq	graph(%rip), %rsi
	movq	%rcx, 152(%rsp)
	imulq	$502, %rcx, %rcx
	addq	%rsi, %rcx
	xorl	%esi, %esi
	movq	%rcx, 48(%rsp)
	.p2align 4,,10
	.p2align 3
.L32:
	movq	48(%rsp), %rdi
	movl	%esi, 80(%rsp)
	cmpb	$0, (%rdi,%rsi)
	je	.L18
	cmpb	$0, (%rdx,%rsi)
	jne	.L18
	movl	(%r11,%rsi,4), %ecx
	movb	$1, (%rdx,%rsi)
	movl	%ecx, 84(%rsp)
	testl	%ecx, %ecx
	js	.L68
	movslq	84(%rsp), %rcx
	leaq	graph(%rip), %rdi
	movq	%rsi, 104(%rsp)
	xorl	%r12d, %r12d
	movq	%rcx, 112(%rsp)
	imulq	$502, %rcx, %rcx
	addq	%rcx, %rdi
	movq	%rdi, 8(%rsp)
	.p2align 4,,10
	.p2align 3
.L31:
	movq	8(%rsp), %rdi
	movl	%r12d, 20(%rsp)
	cmpb	$0, (%rdi,%r12)
	je	.L20
	cmpb	$0, (%rdx,%r12)
	jne	.L20
	movl	(%r11,%r12,4), %edi
	movb	$1, (%rdx,%r12)
	movl	%edi, 36(%rsp)
	testl	%edi, %edi
	js	.L69
	movslq	36(%rsp), %rcx
	movq	%r12, 56(%rsp)
	leaq	graph(%rip), %rdi
	xorl	%ebp, %ebp
	imulq	$502, %rcx, %r15
	movq	%rcx, 64(%rsp)
	addq	%rdi, %r15
	.p2align 4,,10
	.p2align 3
.L30:
	cmpb	$0, (%r15,%rbp)
	movl	%ebp, 32(%rsp)
	je	.L22
	cmpb	$0, (%rdx,%rbp)
	jne	.L22
	movl	(%r11,%rbp,4), %r10d
	movb	$1, (%rdx,%rbp)
	testl	%r10d, %r10d
	js	.L70
	movslq	%r10d, %r8
	leaq	graph(%rip), %rdi
	xorl	%ebx, %ebx
	imulq	$502, %r8, %r14
	addq	%rdi, %r14
	.p2align 4,,10
	.p2align 3
.L29:
	cmpb	$0, (%r14,%rbx)
	movl	%ebx, %ecx
	je	.L24
	cmpb	$0, (%rdx,%rbx)
	jne	.L24
	movl	(%r11,%rbx,4), %r9d
	movb	$1, (%rdx,%rbx)
	testl	%r9d, %r9d
	js	.L71
	movslq	%r9d, %rdi
	xorl	%r13d, %r13d
	imulq	$502, %rdi, %rsi
	movq	%rdi, 24(%rsp)
	leaq	graph(%rip), %rdi
	addq	%rdi, %rsi
	.p2align 4,,10
	.p2align 3
.L28:
	cmpb	$0, (%rsi,%r13)
	movl	%r13d, %r12d
	je	.L26
	cmpb	$0, (%rdx,%r13)
	jne	.L26
	movl	(%r11,%r13,4), %edi
	movq	%rsi, 72(%rsp)
	movb	$1, (%rdx,%r13)
	testl	%edi, %edi
	js	.L27
	movq	%r8, 248(%rsp)
	movl	%ecx, 244(%rsp)
	movl	%r9d, 240(%rsp)
	movl	%r10d, 236(%rsp)
	call	bpm
	movl	236(%rsp), %r10d
	movl	240(%rsp), %r9d
	leaq	matchR(%rip), %r11
	testl	%eax, %eax
	movl	244(%rsp), %ecx
	movq	248(%rsp), %r8
	jne	.L27
	movl	n(%rip), %eax
	movq	72(%rsp), %rsi
	leaq	seen(%rip), %rdx
	.p2align 4,,10
	.p2align 3
.L26:
	addq	$1, %r13
	cmpl	%r13d, %eax
	jg	.L28
.L24:
	addq	$1, %rbx
	cmpl	%ebx, %eax
	jg	.L29
.L22:
	addq	$1, %rbp
	cmpl	%ebp, %eax
	jg	.L30
	movq	56(%rsp), %r12
.L20:
	addq	$1, %r12
	cmpl	%r12d, %eax
	jg	.L31
	movq	104(%rsp), %rsi
.L18:
	addq	$1, %rsi
	cmpl	%esi, %eax
	jg	.L32
.L16:
	addq	$1, 40(%rsp)
	movq	40(%rsp), %rsi
	cmpl	%esi, %eax
	jg	.L33
.L14:
	addq	$1, 88(%rsp)
	movq	88(%rsp), %rsi
	cmpl	%esi, %eax
	jg	.L34
.L12:
	addq	$1, 136(%rsp)
	movq	136(%rsp), %rdi
	cmpl	%edi, %eax
	jg	.L35
.L10:
	addq	$1, 144(%rsp)
	movq	144(%rsp), %rcx
	cmpl	%ecx, %eax
	jg	.L36
.L37:
	xorl	%eax, %eax
.L7:
	addq	$264, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 56
	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
.L27:
	.cfi_restore_state
	movq	24(%rsp), %rax
	leaq	matchL(%rip), %rdx
	movq	%r8, %rsi
	movl	%r9d, %r8d
	movl	%r10d, %r9d
	movl	%ecx, %r10d
	movl	%r12d, (%rdx,%rax,4)
	movslq	%r12d, %rax
	movl	%r8d, (%r11,%rax,4)
.L25:
	movslq	%r10d, %rax
	movl	%r10d, (%rdx,%rsi,4)
	movl	%r9d, (%r11,%rax,4)
.L23:
	movq	64(%rsp), %rsi
	movslq	32(%rsp), %rax
	movl	%eax, (%rdx,%rsi,4)
	movl	36(%rsp), %esi
	movl	%esi, (%r11,%rax,4)
.L21:
	movslq	20(%rsp), %rax
	movq	112(%rsp), %rcx
	movl	84(%rsp), %esi
	movl	%eax, (%rdx,%rcx,4)
	movl	%esi, (%r11,%rax,4)
.L19:
	movslq	80(%rsp), %rax
	movq	152(%rsp), %rcx
	movl	124(%rsp), %esi
	movl	%eax, (%rdx,%rcx,4)
	movl	%esi, (%r11,%rax,4)
.L17:
	movslq	120(%rsp), %rax
	movq	216(%rsp), %rdi
	movl	172(%rsp), %ecx
	movl	%eax, (%rdx,%rdi,4)
	movl	%ecx, (%r11,%rax,4)
.L15:
	movslq	160(%rsp), %rax
	movq	208(%rsp), %rsi
	movl	168(%rsp), %edi
	movl	%eax, (%rdx,%rsi,4)
	movl	%edi, (%r11,%rax,4)
.L13:
	movslq	232(%rsp), %rax
	movq	200(%rsp), %rcx
	movl	164(%rsp), %esi
	movl	%eax, (%rdx,%rcx,4)
	movl	%esi, (%r11,%rax,4)
.L11:
	movslq	180(%rsp), %rax
	movq	224(%rsp), %rdi
	movl	%eax, (%rdx,%rdi,4)
	movl	176(%rsp), %edx
	movl	%edx, (%r11,%rax,4)
	movl	$1, %eax
	jmp	.L7
	.p2align 4,,10
	.p2align 3
.L71:
	movl	%r10d, %r9d
	movq	%r8, %rsi
	leaq	matchL(%rip), %rdx
	movl	%ebx, %r10d
	jmp	.L25
.L70:
	leaq	matchL(%rip), %rdx
	jmp	.L23
.L69:
	leaq	matchL(%rip), %rdx
	jmp	.L21
.L68:
	leaq	matchL(%rip), %rdx
	jmp	.L19
.L67:
	leaq	matchL(%rip), %rdx
	jmp	.L17
.L66:
	leaq	matchL(%rip), %rdx
	jmp	.L15
.L65:
	leaq	matchL(%rip), %rdx
	jmp	.L13
.L64:
	leaq	matchL(%rip), %rdx
	jmp	.L11
	.cfi_endproc
.LFE36:
	.size	bpm, .-bpm
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC0:
	.string	"%d"
.LC1:
	.string	"%d\n"
.LC2:
	.string	"%d%d"
	.section	.text.startup,"ax",@progbits
	.p2align 4
	.globl	main
	.type	main, @function
main:
.LFB37:
	.cfi_startproc
	endbr64
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	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
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	leaq	matchR(%rip), %rbp
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	leaq	seen(%rip), %rbx
	subq	$40, %rsp
	.cfi_def_cfa_offset 96
.L73:
	xorl	%eax, %eax
	leaq	n(%rip), %rdx
	leaq	m(%rip), %rsi
	leaq	.LC2(%rip), %rdi
	call	__isoc99_scanf@PLT
	testl	%eax, %eax
	je	.L99
	movl	m(%rip), %r14d
	testl	%r14d, %r14d
	je	.L99
	leaq	b(%rip), %r13
	movl	$0, %r12d
	jle	.L92
	.p2align 4,,10
	.p2align 3
.L74:
	movq	%r13, %rsi
	leaq	.LC0(%rip), %rdi
	xorl	%eax, %eax
	addl	$1, %r12d
	call	__isoc99_scanf@PLT
	movl	m(%rip), %r14d
	addq	$4, %r13
	cmpl	%r12d, %r14d
	jg	.L74
.L92:
	movslq	n(%rip), %rax
	testl	%eax, %eax
	jle	.L75
	leaq	r(%rip), %r12
	xorl	%r13d, %r13d
	movq	%r12, %r14
	.p2align 4,,10
	.p2align 3
.L76:
	movq	%r14, %rsi
	leaq	.LC0(%rip), %rdi
	xorl	%eax, %eax
	addl	$1, %r13d
	call	__isoc99_scanf@PLT
	movl	n(%rip), %eax
	addq	$4, %r14
	cmpl	%r13d, %eax
	jg	.L76
	movslq	m(%rip), %r13
	movslq	%eax, %r10
	leaq	0(,%r10,4), %rdi
	movq	%r13, %r14
	movq	%rdi, 8(%rsp)
	salq	$2, %r13
	testl	%r14d, %r14d
	jle	.L77
	testl	%eax, %eax
	jle	.L78
	leaq	b(%rip), %r11
	leal	-1(%r14), %eax
	leaq	4(%r11), %rdx
	leaq	graph(%rip), %rdi
	leaq	(%rdx,%rax,4), %r8
	.p2align 4,,10
	.p2align 3
.L79:
	movl	(%r11), %r9d
	xorl	%esi, %esi
	.p2align 4,,10
	.p2align 3
.L82:
	movl	(%r12,%rsi,4), %edx
	testl	%edx, %edx
	je	.L96
	movl	%r9d, %eax
	.p2align 4,,10
	.p2align 3
.L81:
	movl	%edx, %ecx
	cltd
	idivl	%ecx
	movl	%ecx, %eax
	testl	%edx, %edx
	jne	.L81
	cmpl	$1, %ecx
	setg	(%rdi,%rsi)
	addq	$1, %rsi
	cmpq	%r10, %rsi
	jne	.L82
.L118:
	addq	$4, %r11
	addq	$502, %rdi
	cmpq	%r8, %r11
	jne	.L79
.L78:
	movq	%r13, %rdx
	movl	$2008, %ecx
	movl	$-1, %esi
	xorl	%r15d, %r15d
	leaq	matchL(%rip), %rdi
	leaq	graph(%rip), %r13
	call	__memset_chk@PLT
	movq	8(%rsp), %rdx
	movl	$2008, %ecx
	movq	%rbp, %rdi
	movl	$-1, %esi
	call	__memset_chk@PLT
	leaq	matchL(%rip), %rax
	movl	$0, 28(%rsp)
	movq	%rax, 16(%rsp)
	.p2align 4,,10
	.p2align 3
.L94:
	movslq	n(%rip), %rdx
	movl	$502, %ecx
	xorl	%esi, %esi
	movq	%rbx, %rdi
	movl	%edx, 8(%rsp)
	call	__memset_chk@PLT
	movl	8(%rsp), %r8d
	testl	%r8d, %r8d
	jle	.L85
	xorl	%r14d, %r14d
	.p2align 4,,10
	.p2align 3
.L89:
	cmpb	$0, 0(%r13,%r14)
	movl	%r14d, %r12d
	je	.L86
	cmpb	$0, (%rbx,%r14)
	jne	.L86
	movl	0(%rbp,%r14,4), %edi
	movb	$1, (%rbx,%r14)
	testl	%edi, %edi
	js	.L87
	call	bpm
	testl	%eax, %eax
	jne	.L87
	movl	n(%rip), %r8d
.L86:
	addq	$1, %r14
	cmpl	%r14d, %r8d
	jg	.L89
	movl	%r15d, %eax
	movl	m(%rip), %r14d
	addl	$1, %eax
	movl	%eax, %r15d
	cmpl	%eax, %r14d
	jle	.L93
.L95:
	addq	$4, 16(%rsp)
	addq	$502, %r13
	jmp	.L94
	.p2align 4,,10
	.p2align 3
.L96:
	movl	%r9d, %ecx
	cmpl	$1, %ecx
	setg	(%rdi,%rsi)
	addq	$1, %rsi
	cmpq	%r10, %rsi
	jne	.L82
	jmp	.L118
.L87:
	movq	16(%rsp), %rax
	movl	m(%rip), %r14d
	movslq	%r12d, %rdx
	movl	%r15d, 0(%rbp,%rdx,4)
	movl	%r12d, (%rax)
	movl	%r15d, %eax
	addl	$1, %eax
	addl	$1, 28(%rsp)
	movl	%eax, %r15d
	cmpl	%eax, %r14d
	jg	.L95
.L93:
	movl	28(%rsp), %edx
	leaq	.LC1(%rip), %rsi
	movl	$1, %edi
	xorl	%eax, %eax
	call	__printf_chk@PLT
	jmp	.L73
.L75:
	movslq	%r14d, %r13
	salq	$2, %rax
	movq	%rax, 8(%rsp)
	salq	$2, %r13
	testl	%r14d, %r14d
	jg	.L78
.L77:
	movl	$2008, %ecx
	movq	%r13, %rdx
	movl	$-1, %esi
	leaq	matchL(%rip), %rdi
	call	__memset_chk@PLT
	movq	8(%rsp), %rdx
	movl	$2008, %ecx
	movq	%rbp, %rdi
	movl	$-1, %esi
	call	__memset_chk@PLT
	movl	$0, 28(%rsp)
	jmp	.L93
.L99:
	addq	$40, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 56
	xorl	%eax, %eax
	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
.L85:
	.cfi_restore_state
	movl	%r15d, %r12d
	addl	$1, %r12d
	cmpl	%r14d, %r12d
	jge	.L93
	.p2align 4,,10
	.p2align 3
.L83:
	movslq	n(%rip), %rdx
	xorl	%esi, %esi
	movq	%rbx, %rdi
	addl	$1, %r12d
	movl	$502, %ecx
	call	__memset_chk@PLT
	cmpl	%r14d, %r12d
	jl	.L83
	jmp	.L93
	.cfi_endproc
.LFE37:
	.size	main, .-main
	.globl	r
	.bss
	.align 32
	.type	r, @object
	.size	r, 2008
r:
	.zero	2008
	.globl	b
	.align 32
	.type	b, @object
	.size	b, 2008
b:
	.zero	2008
	.globl	matchR
	.align 32
	.type	matchR, @object
	.size	matchR, 2008
matchR:
	.zero	2008
	.globl	matchL
	.align 32
	.type	matchL, @object
	.size	matchL, 2008
matchL:
	.zero	2008
	.globl	seen
	.align 32
	.type	seen, @object
	.size	seen, 502
seen:
	.zero	502
	.globl	graph
	.align 32
	.type	graph, @object
	.size	graph, 252004
graph:
	.zero	252004
	.globl	n
	.align 4
	.type	n, @object
	.size	n, 4
n:
	.zero	4
	.globl	m
	.align 4
	.type	m, @object
	.size	m, 4
m:
	.zero	4
	.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:

// Aizu 1163: Cards
// 2017.9.15 bal4u@uu

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

#define M 502
#define N 502

int m, n;
char graph[M][N], seen[N];
int matchL[M], matchR[N];

int b[M], r[N];

int gcd(int a, int b)
{
	int r;
	while (b != 0) r = a % b, a = b, b = r;
	return a;
}

int bpm(int u)
{
	int v;

	for (v = 0; v < n; v++) if (graph[u][v]) {
		if (seen[v]) continue;
		seen[v] = 1;
		if (matchR[v] < 0 || bpm(matchR[v])) {
			matchL[u] = v, matchR[v] = u;
			return 1;
		}
	}
	return 0;
}

int main()
{
	int i, j, cnt;

	while (scanf("%d%d", &m, &n) && m) {
		for (i = 0; i < m; i++) scanf("%d", b+i);
		for (j = 0; j < n; j++) scanf("%d", r+j);
	    for (i = 0; i < m; i++) for (j = 0; j < n; j++) graph[i][j] = (gcd(b[i], r[j]) > 1);
		memset(matchL, -1, m*sizeof(matchL[0]));
		memset(matchR, -1, n*sizeof(matchR[0]));
		for (cnt = 0, i = 0; i < m; i++) { memset(seen, 0, n); if (bpm(i)) cnt++; }
		printf("%d\n", cnt);
	}
	return 0;
}
4 3
2 6 6 15
2 3 5
2 3
4 9
8 16 32
4 2
4 9 11 13
5 7
5 5
2 3 5 1001 1001
7 11 13 30 30
10 10
2 3 5 7 9 11 13 15 17 29
4 6 10 14 18 22 26 30 34 38
20 20
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
100 100
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
117 755 835 683 52 369 302 424 513 870
75 874 299 228 140 361 30 342 750 819
761 123 804 325 952 405 578 517 49 457
932 941 988 767 624 41 912 702 241 426
351 92 300 648 318 216 785 347 556 535
166 318 434 746 419 386 928 996 680 975
231 390 916 220 933 319 37 846 797 54
272 924 145 348 350 239 563 135 362 119
446 305 213 879 51 631 43 755 405 499
509 412 887 203 408 821 298 443 445 96
274 715 796 417 839 147 654 402 280 17
298 725 98 287 382 923 694 201 679 99
699 188 288 364 389 694 185 464 138 406
558 188 897 354 603 737 277 35 139 556
826 213 59 922 499 217 846 193 416 525
69 115 489 355 256 654 49 553 118 961
0 0
 4 3
2 6 6 15
2 3 5
2 3
4 9
8 16 32
4 2
4 9 11 13
5 7
5 5
2 3 5 1001 1001
7 11 13 30 30
10 10
2 3 5 7 9 11 13 15 17 29
4 6 10 14 18 22 26 30 34 38
20 20
195 144 903 63 137 513 44 626 75 473
876 421 909 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
100 100
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
117 755 835 683 52 369 302 424 513 870
75 874 299 228 140 361 30 342 750 819
761 123 804 325 555 405 578 517 49 457
932 941 988 767 624 41 912 702 241 426
351 92 300 648 600 216 785 347 556 535
166 318 434 746 419 386 928 996 680 975
231 390 916 220 933 319 37 846 797 54
272 924 145 348 350 239 563 135 362 119
446 305 213 879 51 631 43 372 405 499
509 412 887 203 408 821 298 443 445 96
274 715 796 417 839 147 654 402 280 17
298 725 98 287 382 923 694 201 679 99
699 188 288 364 389 694 185 464 138 406
558 188 897 354 603 737 277 35 139 556
826 213 59 922 499 413 846 193 416 525
69 115 489 355 256 654 49 553 118 961
0 0
 4 3
2 6 6 15
2 3 5
2 3
4 9
8 16 32
4 2
4 9 11 13
5 7
5 5
2 3 5 1001 1001
7 11 13 30 30
10 10
2 3 5 7 9 11 13 15 17 29
4 6 10 14 18 22 26 30 34 38
20 20
195 144 903 63 137 513 44 626 75 473
876 421 909 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
100 100
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
117 755 835 683 52 369 302 424 513 870
75 874 299 228 140 361 30 342 750 819
761 123 804 325 555 405 578 517 49 457
932 941 988 767 624 41 912 702 241 426
351 92 300 648 600 216 785 347 556 535
166 318 434 746 419 386 928 996 680 975
231 390 916 220 933 319 37 846 797 54
272 924 145 348 350 239 563 135 362 119
446 305 213 879 51 631 43 372 405 499
509 412 887 203 408 821 298 443 445 96
274 715 796 417 64 147 654 402 280 17
298 725 98 287 382 923 694 201 679 99
699 188 288 364 389 694 185 464 138 406
558 188 897 354 603 737 277 35 139 556
826 213 59 922 499 413 846 193 416 525
69 115 489 355 256 654 49 553 118 961
0 0
 4 3
2 6 6 15
2 3 5
2 3
4 9
8 16 22
4 2
4 9 11 13
5 7
5 5
2 3 5 1001 1001
7 11 13 30 30
10 10
2 3 5 7 9 11 13 15 17 29
4 6 10 14 18 22 26 30 34 38
20 20
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
100 100
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
117 755 835 683 52 369 302 424 513 870
75 874 299 228 140 361 30 342 750 819
761 123 804 325 952 405 578 517 49 457
932 941 988 767 624 41 912 702 241 426
351 92 300 648 318 216 785 347 556 535
166 318 434 746 419 386 928 996 680 975
231 390 916 220 933 319 37 846 797 54
272 924 145 348 350 239 563 135 362 119
446 305 213 879 51 631 43 755 405 499
509 412 887 203 408 821 298 443 445 96
274 715 796 417 839 147 654 402 280 17
298 725 98 287 382 923 694 201 679 99
699 188 288 364 389 694 185 464 138 406
558 188 897 354 603 737 277 35 139 556
826 213 59 922 499 217 846 193 416 525
69 115 489 355 256 654 49 439 118 961
0 0
 4 3
2 6 6 15
2 3 5
2 3
4 9
8 16 32
4 2
4 9 11 13
5 7
5 5
2 3 5 1000 1001
7 11 13 30 30
10 10
2 3 5 7 9 11 13 28 17 29
4 6 10 14 18 22 26 30 34 38
20 20
195 144 903 63 137 513 44 626 75 473
876 421 909 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
100 100
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
117 755 835 683 52 369 302 424 513 870
75 874 299 228 140 361 30 456 750 819
761 123 804 325 555 405 578 517 49 457
932 941 988 767 624 41 912 702 241 426
351 92 300 648 600 216 785 347 556 535
166 318 434 746 419 386 928 996 680 975
231 390 916 220 1255 319 20 846 797 54
272 924 145 348 350 239 563 135 362 119
446 305 213 879 51 631 43 372 405 499
509 412 887 203 408 821 298 443 445 67
274 715 796 417 64 147 654 402 280 17
298 725 98 287 382 923 694 201 679 99
699 188 288 364 389 694 185 464 138 406
558 188 897 354 603 737 277 35 139 556
826 213 59 922 499 413 846 193 416 525
69 115 489 355 256 654 49 553 118 961
0 0
 4 3
2 6 6 15
2 3 5
2 3
4 9
8 16 22
4 2
4 9 11 13
5 7
5 5
2 3 5 1001 1001
7 11 13 30 30
10 10
2 3 5 7 9 11 5 15 17 9
4 6 10 14 18 22 26 30 34 38
20 20
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
100 100
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
117 755 835 683 52 369 302 424 513 870
75 874 299 228 140 361 30 342 750 819
761 123 804 325 952 405 578 517 49 457
932 941 988 767 624 41 912 702 241 426
351 92 300 648 318 216 785 347 556 535
166 318 434 746 419 386 928 996 680 975
231 390 916 220 933 319 37 846 797 54
272 924 145 348 350 239 563 135 362 119
446 305 213 879 51 631 43 755 405 499
509 412 887 203 408 821 298 443 445 96
274 715 796 417 839 147 654 402 280 17
298 725 98 287 382 923 694 201 679 99
699 188 288 364 389 694 185 464 138 406
558 188 897 354 603 737 277 35 139 556
826 213 59 922 499 217 846 193 416 525
69 115 489 355 256 654 49 439 118 961
0 0
 4 3
2 6 6 15
2 3 5
2 3
4 9
8 16 32
4 2
4 9 11 13
5 7
5 5
2 3 5 1001 1001
7 11 13 30 30
10 10
2 3 5 7 9 11 13 15 17 29
4 6 10 14 18 22 26 30 34 38
20 20
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 107 823 477 565 866 879 638
100 100
195 144 903 63 137 513 44 320 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 1470 477 565 866 879 638
117 755 835 683 52 369 302 424 513 870
75 874 299 228 140 361 30 342 750 819
761 123 804 325 952 405 578 517 49 457
932 941 988 767 624 41 912 702 241 426
351 8 300 648 600 216 785 347 556 535
166 318 434 746 419 386 928 996 680 975
231 390 916 220 933 319 37 846 797 54
272 924 145 348 350 239 563 135 362 119
446 305 213 879 51 631 43 755 405 499
509 412 887 203 408 821 298 443 445 96
274 715 796 417 839 147 654 402 280 17
298 725 98 287 382 923 694 201 679 99
699 188 288 364 389 694 185 464 138 406
558 188 897 354 603 737 277 35 139 556
826 213 59 922 499 413 846 193 416 525
69 115 489 355 256 654 49 553 118 961
0 0
 4 3
2 6 6 15
2 3 5
2 3
4 9
8 16 22
4 2
4 9 11 13
5 7
5 5
2 3 5 1001 1001
7 11 13 30 30
10 10
2 3 5 7 9 11 5 15 17 9
4 1 10 14 18 22 26 30 34 38
20 20
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
100 100
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
117 755 835 683 52 369 302 424 513 870
75 874 299 228 140 361 30 342 750 819
761 123 804 325 1606 405 578 517 49 457
932 941 988 767 624 41 912 702 241 426
351 92 300 648 318 216 785 347 556 535
166 318 434 746 419 386 928 996 680 975
231 390 916 220 933 319 37 846 797 54
272 924 145 348 350 239 563 135 362 119
446 305 213 879 51 631 43 755 405 499
509 412 887 203 408 821 298 443 445 96
274 715 796 417 839 147 654 402 280 17
298 725 98 287 382 923 694 201 679 99
699 188 288 364 389 694 185 464 138 406
558 188 897 354 603 737 277 35 139 556
826 213 59 922 499 217 846 193 416 525
69 115 489 355 256 654 49 439 118 961
0 0
 4 3
2 6 6 15
2 3 5
2 3
4 9
8 16 32
4 2
4 9 11 13
5 7
5 5
2 3 5 1001 1001
2 11 13 30 30
10 10
2 3 5 7 9 11 13 15 17 29
4 6 10 14 18 22 26 30 34 38
20 20
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 107 823 477 565 866 879 638
100 100
195 144 903 63 137 513 44 320 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 1470 477 565 866 879 638
117 755 835 683 52 369 302 424 513 870
75 874 299 228 140 361 30 342 750 819
761 123 804 325 952 405 578 517 49 457
932 941 988 767 624 41 912 702 241 426
351 8 300 648 600 216 785 347 556 535
166 318 434 746 419 386 928 996 680 975
231 390 916 220 933 319 37 846 797 54
272 924 145 348 350 239 563 135 362 119
446 305 213 879 51 631 43 755 405 499
509 412 887 203 408 821 298 443 445 96
274 715 796 417 839 147 654 402 280 17
298 725 98 287 382 923 694 201 679 99
699 202 288 364 389 694 185 464 138 406
558 188 897 354 603 737 277 35 139 556
826 213 59 922 499 413 846 193 416 525
69 115 489 355 256 654 49 553 118 961
0 0
 4 3
2 6 6 15
2 3 5
2 3
4 9
8 16 32
4 2
4 9 11 13
5 7
5 5
2 3 5 1001 1001
7 11 13 30 30
10 10
2 3 5 7 9 11 13 28 17 29
4 6 10 14 18 22 26 30 34 38
20 20
195 144 903 126 137 513 44 626 75 473
876 421 909 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 809 565 866 879 638
100 100
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 828
373 984 564 54 823 477 565 866 879 638
117 755 835 683 52 369 302 424 513 870
75 874 299 228 140 361 30 342 750 819
761 123 804 325 555 405 578 517 49 457
932 941 988 767 624 41 912 702 241 426
351 92 300 648 600 216 785 347 556 535
166 318 434 746 419 386 928 996 680 975
231 390 916 220 928 319 37 846 797 54
272 924 145 348 350 239 563 135 362 119
446 305 213 879 51 631 43 372 405 499
509 412 887 203 408 821 298 443 445 67
274 715 139 243 64 147 654 402 280 17
298 725 98 287 382 923 694 201 679 99
699 188 288 364 389 694 185 464 138 406
558 188 897 354 603 737 277 35 139 556
826 213 59 922 499 413 846 193 416 525
69 115 489 355 256 654 49 553 118 961
0 0

3
1
0
4
9
18
86
 3
1
0
4
9
18
87
 3
1
0
4
9
18
88
 3
1
0
4
9
18
85
 3
1
0
3
9
18
88
 3
1
0
4
8
18
85
 3
1
0
4
9
17
86
 3
1
0
4
7
18
85
 3
1
0
5
9
17
86
 3
1
0
4
9
17
87

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

```c
// Aizu 1163: Cards
// 2017.9.15 bal4u@uu

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

#define M 502
#define N 502

int m, n;
char graph[M][N], seen[N];
int matchL[M], matchR[N];

int b[M], r[N];

int gcd(int a, int b)
{
	int r;
	while (b != 0) r = a % b, a = b, b = r;
	return a;
}

int bpm(int u)
{
	int v;

	for (v = 0; v < n; v++) if (graph[u][v]) {
		if (seen[v]) continue;
		seen[v] = 1;
		if (matchR[v] < 0 || bpm(matchR[v])) {
			matchL[u] = v, matchR[v] = u;
			return 1;
		}
	}
	return 0;
}

int main()
{
	int i, j, cnt;

	while (scanf("%d%d", &m, &n) && m) {
		for (i = 0; i < m; i++) scanf("%d", b+i);
		for (j = 0; j < n; j++) scanf("%d", r+j);
	    for (i = 0; i < m; i++) for (j = 0; j < n; j++) graph[i][j] = (gcd(b[i], r[j]) > 1);
		memset(matchL, -1, m*sizeof(matchL[0]));
		memset(matchR, -1, n*sizeof(matchR[0]));
		for (cnt = 0, i = 0; i < m; i++) { memset(seen, 0, n); if (bpm(i)) cnt++; }
		printf("%d\n", cnt);
	}
	return 0;
}```

Unoptimized Assembly Code:

```assembly
	.file	"temp.c"
	.text
	.globl	m
	.bss
	.align 4
	.type	m, @object
	.size	m, 4
m:
	.zero	4
	.globl	n
	.align 4
	.type	n, @object
	.size	n, 4
n:
	.zero	4
	.globl	graph
	.align 32
	.type	graph, @object
	.size	graph, 252004
graph:
	.zero	252004
	.globl	seen
	.align 32
	.type	seen, @object
	.size	seen, 502
seen:
	.zero	502
	.globl	matchL
	.align 32
	.type	matchL, @object
	.size	matchL, 2008
matchL:
	.zero	2008
	.globl	matchR
	.align 32
	.type	matchR, @object
	.size	matchR, 2008
matchR:
	.zero	2008
	.globl	b
	.align 32
	.type	b, @object
	.size	b, 2008
b:
	.zero	2008
	.globl	r
	.align 32
	.type	r, @object
	.size	r, 2008
r:
	.zero	2008
	.text
	.globl	gcd
	.type	gcd, @function
gcd:
.LFB0:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movl	%edi, -20(%rbp)
	movl	%esi, -24(%rbp)
	jmp	.L2
.L3:
	movl	-20(%rbp), %eax
	cltd
	idivl	-24(%rbp)
	movl	%edx, -4(%rbp)
	movl	-24(%rbp), %eax
	movl	%eax, -20(%rbp)
	movl	-4(%rbp), %eax
	movl	%eax, -24(%rbp)
.L2:
	cmpl	$0, -24(%rbp)
	jne	.L3
	movl	-20(%rbp), %eax
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE0:
	.size	gcd, .-gcd
	.globl	bpm
	.type	bpm, @function
bpm:
.LFB1:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$32, %rsp
	movl	%edi, -20(%rbp)
	movl	$0, -4(%rbp)
	jmp	.L6
.L11:
	movl	-4(%rbp), %eax
	movslq	%eax, %rdx
	movl	-20(%rbp), %eax
	cltq
	imulq	$502, %rax, %rax
	addq	%rax, %rdx
	leaq	graph(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	testb	%al, %al
	je	.L7
	movl	-4(%rbp), %eax
	cltq
	leaq	seen(%rip), %rdx
	movzbl	(%rax,%rdx), %eax
	testb	%al, %al
	jne	.L12
	movl	-4(%rbp), %eax
	cltq
	leaq	seen(%rip), %rdx
	movb	$1, (%rax,%rdx)
	movl	-4(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	matchR(%rip), %rax
	movl	(%rdx,%rax), %eax
	testl	%eax, %eax
	js	.L9
	movl	-4(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	matchR(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, %edi
	call	bpm
	testl	%eax, %eax
	je	.L7
.L9:
	movl	-20(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rcx
	leaq	matchL(%rip), %rdx
	movl	-4(%rbp), %eax
	movl	%eax, (%rcx,%rdx)
	movl	-4(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rcx
	leaq	matchR(%rip), %rdx
	movl	-20(%rbp), %eax
	movl	%eax, (%rcx,%rdx)
	movl	$1, %eax
	jmp	.L10
.L12:
	nop
.L7:
	addl	$1, -4(%rbp)
.L6:
	movl	n(%rip), %eax
	cmpl	%eax, -4(%rbp)
	jl	.L11
	movl	$0, %eax
.L10:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE1:
	.size	bpm, .-bpm
	.section	.rodata
.LC0:
	.string	"%d"
.LC1:
	.string	"%d\n"
.LC2:
	.string	"%d%d"
	.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
	subq	$16, %rsp
	jmp	.L14
.L27:
	movl	$0, -12(%rbp)
	jmp	.L15
.L16:
	movl	-12(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	b(%rip), %rax
	addq	%rdx, %rax
	movq	%rax, %rsi
	leaq	.LC0(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	addl	$1, -12(%rbp)
.L15:
	movl	m(%rip), %eax
	cmpl	%eax, -12(%rbp)
	jl	.L16
	movl	$0, -8(%rbp)
	jmp	.L17
.L18:
	movl	-8(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	r(%rip), %rax
	addq	%rdx, %rax
	movq	%rax, %rsi
	leaq	.LC0(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	addl	$1, -8(%rbp)
.L17:
	movl	n(%rip), %eax
	cmpl	%eax, -8(%rbp)
	jl	.L18
	movl	$0, -12(%rbp)
	jmp	.L19
.L22:
	movl	$0, -8(%rbp)
	jmp	.L20
.L21:
	movl	-8(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	r(%rip), %rax
	movl	(%rdx,%rax), %edx
	movl	-12(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rcx
	leaq	b(%rip), %rax
	movl	(%rcx,%rax), %eax
	movl	%edx, %esi
	movl	%eax, %edi
	call	gcd
	cmpl	$1, %eax
	setg	%al
	movl	%eax, %edx
	movl	-8(%rbp), %eax
	movslq	%eax, %rcx
	movl	-12(%rbp), %eax
	cltq
	imulq	$502, %rax, %rax
	addq	%rax, %rcx
	leaq	graph(%rip), %rax
	addq	%rcx, %rax
	movb	%dl, (%rax)
	addl	$1, -8(%rbp)
.L20:
	movl	n(%rip), %eax
	cmpl	%eax, -8(%rbp)
	jl	.L21
	addl	$1, -12(%rbp)
.L19:
	movl	m(%rip), %eax
	cmpl	%eax, -12(%rbp)
	jl	.L22
	movl	m(%rip), %eax
	cltq
	salq	$2, %rax
	movq	%rax, %rdx
	movl	$-1, %esi
	leaq	matchL(%rip), %rax
	movq	%rax, %rdi
	call	memset@PLT
	movl	n(%rip), %eax
	cltq
	salq	$2, %rax
	movq	%rax, %rdx
	movl	$-1, %esi
	leaq	matchR(%rip), %rax
	movq	%rax, %rdi
	call	memset@PLT
	movl	$0, -4(%rbp)
	movl	$0, -12(%rbp)
	jmp	.L23
.L25:
	movl	n(%rip), %eax
	cltq
	movq	%rax, %rdx
	movl	$0, %esi
	leaq	seen(%rip), %rax
	movq	%rax, %rdi
	call	memset@PLT
	movl	-12(%rbp), %eax
	movl	%eax, %edi
	call	bpm
	testl	%eax, %eax
	je	.L24
	addl	$1, -4(%rbp)
.L24:
	addl	$1, -12(%rbp)
.L23:
	movl	m(%rip), %eax
	cmpl	%eax, -12(%rbp)
	jl	.L25
	movl	-4(%rbp), %eax
	movl	%eax, %esi
	leaq	.LC1(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
.L14:
	leaq	n(%rip), %rax
	movq	%rax, %rdx
	leaq	m(%rip), %rax
	movq	%rax, %rsi
	leaq	.LC2(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	testl	%eax, %eax
	je	.L26
	movl	m(%rip), %eax
	testl	%eax, %eax
	jne	.L27
.L26:
	movl	$0, %eax
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE2:
	.size	main, .-main
	.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	m
	.bss
	.align 4
	.type	m, @object
	.size	m, 4
m:
	.zero	4
	.globl	n
	.align 4
	.type	n, @object
	.size	n, 4
n:
	.zero	4
	.globl	graph
	.align 32
	.type	graph, @object
	.size	graph, 252004
graph:
	.zero	252004
	.globl	seen
	.align 32
	.type	seen, @object
	.size	seen, 502
seen:
	.zero	502
	.globl	matchL
	.align 32
	.type	matchL, @object
	.size	matchL, 2008
matchL:
	.zero	2008
	.globl	matchR
	.align 32
	.type	matchR, @object
	.size	matchR, 2008
matchR:
	.zero	2008
	.globl	b
	.align 32
	.type	b, @object
	.size	b, 2008
b:
	.zero	2008
	.globl	r
	.align 32
	.type	r, @object
	.size	r, 2008
r:
	.zero	2008
	.text
	.globl	gcd
	.type	gcd, @function
gcd:
.LFB0:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movl	%edi, -20(%rbp)
	movl	%esi, -24(%rbp)
	jmp	.L2
.L3:
	movl	-20(%rbp), %eax
	cltd
	idivl	-24(%rbp)
	movl	%edx, -4(%rbp)
	movl	-24(%rbp), %eax
	movl	%eax, -20(%rbp)
	movl	-4(%rbp), %eax
	movl	%eax, -24(%rbp)
.L2:
	cmpl	$0, -24(%rbp)
	jne	.L3
	movl	-20(%rbp), %eax
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE0:
	.size	gcd, .-gcd
	.globl	bpm
	.type	bpm, @function
bpm:
.LFB1:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$32, %rsp
	movl	%edi, -20(%rbp)
	movl	$0, -4(%rbp)
	jmp	.L6
.L11:
	movl	-4(%rbp), %eax
	movslq	%eax, %rdx
	movl	-20(%rbp), %eax
	cltq
	imulq	$502, %rax, %rax
	addq	%rax, %rdx
	leaq	graph(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	testb	%al, %al
	je	.L7
	movl	-4(%rbp), %eax
	cltq
	leaq	seen(%rip), %rdx
	movzbl	(%rax,%rdx), %eax
	testb	%al, %al
	jne	.L12
	movl	-4(%rbp), %eax
	cltq
	leaq	seen(%rip), %rdx
	movb	$1, (%rax,%rdx)
	movl	-4(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	matchR(%rip), %rax
	movl	(%rdx,%rax), %eax
	testl	%eax, %eax
	js	.L9
	movl	-4(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	matchR(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, %edi
	call	bpm
	testl	%eax, %eax
	je	.L7
.L9:
	movl	-20(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rcx
	leaq	matchL(%rip), %rdx
	movl	-4(%rbp), %eax
	movl	%eax, (%rcx,%rdx)
	movl	-4(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rcx
	leaq	matchR(%rip), %rdx
	movl	-20(%rbp), %eax
	movl	%eax, (%rcx,%rdx)
	movl	$1, %eax
	jmp	.L10
.L12:
	nop
.L7:
	addl	$1, -4(%rbp)
.L6:
	movl	n(%rip), %eax
	cmpl	%eax, -4(%rbp)
	jl	.L11
	movl	$0, %eax
.L10:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE1:
	.size	bpm, .-bpm
	.section	.rodata
.LC0:
	.string	"%d"
.LC1:
	.string	"%d\n"
.LC2:
	.string	"%d%d"
	.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
	subq	$16, %rsp
	jmp	.L14
.L27:
	movl	$0, -12(%rbp)
	jmp	.L15
.L16:
	movl	-12(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	b(%rip), %rax
	addq	%rdx, %rax
	movq	%rax, %rsi
	leaq	.LC0(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	addl	$1, -12(%rbp)
.L15:
	movl	m(%rip), %eax
	cmpl	%eax, -12(%rbp)
	jl	.L16
	movl	$0, -8(%rbp)
	jmp	.L17
.L18:
	movl	-8(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	r(%rip), %rax
	addq	%rdx, %rax
	movq	%rax, %rsi
	leaq	.LC0(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	addl	$1, -8(%rbp)
.L17:
	movl	n(%rip), %eax
	cmpl	%eax, -8(%rbp)
	jl	.L18
	movl	$0, -12(%rbp)
	jmp	.L19
.L22:
	movl	$0, -8(%rbp)
	jmp	.L20
.L21:
	movl	-8(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	r(%rip), %rax
	movl	(%rdx,%rax), %edx
	movl	-12(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rcx
	leaq	b(%rip), %rax
	movl	(%rcx,%rax), %eax
	movl	%edx, %esi
	movl	%eax, %edi
	call	gcd
	cmpl	$1, %eax
	setg	%al
	movl	%eax, %edx
	movl	-8(%rbp), %eax
	movslq	%eax, %rcx
	movl	-12(%rbp), %eax
	cltq
	imulq	$502, %rax, %rax
	addq	%rax, %rcx
	leaq	graph(%rip), %rax
	addq	%rcx, %rax
	movb	%dl, (%rax)
	addl	$1, -8(%rbp)
.L20:
	movl	n(%rip), %eax
	cmpl	%eax, -8(%rbp)
	jl	.L21
	addl	$1, -12(%rbp)
.L19:
	movl	m(%rip), %eax
	cmpl	%eax, -12(%rbp)
	jl	.L22
	movl	m(%rip), %eax
	cltq
	salq	$2, %rax
	movq	%rax, %rdx
	movl	$-1, %esi
	leaq	matchL(%rip), %rax
	movq	%rax, %rdi
	call	memset@PLT
	movl	n(%rip), %eax
	cltq
	salq	$2, %rax
	movq	%rax, %rdx
	movl	$-1, %esi
	leaq	matchR(%rip), %rax
	movq	%rax, %rdi
	call	memset@PLT
	movl	$0, -4(%rbp)
	movl	$0, -12(%rbp)
	jmp	.L23
.L25:
	movl	n(%rip), %eax
	cltq
	movq	%rax, %rdx
	movl	$0, %esi
	leaq	seen(%rip), %rax
	movq	%rax, %rdi
	call	memset@PLT
	movl	-12(%rbp), %eax
	movl	%eax, %edi
	call	bpm
	testl	%eax, %eax
	je	.L24
	addl	$1, -4(%rbp)
.L24:
	addl	$1, -12(%rbp)
.L23:
	movl	m(%rip), %eax
	cmpl	%eax, -12(%rbp)
	jl	.L25
	movl	-4(%rbp), %eax
	movl	%eax, %esi
	leaq	.LC1(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
.L14:
	leaq	n(%rip), %rax
	movq	%rax, %rdx
	leaq	m(%rip), %rax
	movq	%rax, %rsi
	leaq	.LC2(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	testl	%eax, %eax
	je	.L26
	movl	m(%rip), %eax
	testl	%eax, %eax
	jne	.L27
.L26:
	movl	$0, %eax
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE2:
	.size	main, .-main
	.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:
