题目描述

桌子上现在有m张蓝色卡片和n张红色卡片，每张卡片上有一个大于1的整数。现在你要从桌子上拿走一些卡片，分若干次拿。每次只能拿走一组卡片：这组卡片颜色不同，并且两张卡片上面的数字的最大公约数大于1。问：最多可以从桌上拿走多少组卡片。

输入格式

每个输入文件中包含多组测试数据，每个文件中测试数据的数目不超过100。

文件的第一行读入一个整数T，为数据组数。

每组数据的格式如下：

m n

b1 b2 … bm

r1 r2 … rn

第二行给出每张蓝色卡片上面的数字，第三行给出每张红色卡片上的数字。

输出格式

对每组测试数据，输出最多可以拿走多少张卡片。

7
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 439 118 961

3
1
0
4
9
18
85

提示

对100%的数据：1<=t<=100;

1<=m,n<=500;

卡片上的数字大于1，小于10 000 000。