prithivMLmods/Coder-Stat

1 2<h1><font color="#000000">Problem E:</font> Cards</h1>3 4 5<p>6There are many blue cards and red cards on the table.7For each card, an integer number greater than 1 is printed on its face.8The same number may be printed on several cards.9 10</p>11 12<p>13A blue card and a red card can be paired when both of the numbers14printed on them have a common divisor greater than 1.15There may be more than one red card that can be paired with one blue card.16Also, there may be more than one blue card that can be paired with one red card.17When a blue card and a red card are chosen and paired,18these two cards are removed from the whole cards on the table.19</p>20 21 22<center>23<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_2009E1" width=300 ><br>24 25Figure E-1: Four blue cards and three red cards26 27</center>28 29 30<p>31For example, in Figure E-1,32there are four blue cards and three red cards.33Numbers 2, 6, 6 and 15 are printed on the faces of the four blue cards, 34and 2, 3 and 35 are printed on those of the three red cards.35Here, you can make pairs of blue cards and red cards as follows.36First,37the blue card with number 2 on it and the red card with 2 are paired and removed.38Second,39one of the two blue cards with 6 and the red card with 3 are paired and removed.40Finally,41the blue card with 15 and the red card with 35 are paired and removed.42Thus the number of removed pairs is three.43</p>44 45<p>46Note that the total number of the pairs depends on47the way of choosing cards to be paired.48The blue card with 15 and the red card with 3 might be paired 49and removed at the beginning.50In this case, there are only one more pair that can be removed51and the total number of the removed pairs is two.52</p>53 54 55<p>56Your job is to find the largest number of pairs that can be removed from the given set of cards on the table.57</p>58 59 60<h3>Input</h3>61 62 63<p>64The input is a sequence of datasets.65The number of the datasets is less than or equal to 100.66Each dataset is formatted as follows.67</p>68 69 70<p>71<blockquote>72<i>m</i> <i>n</i> <br>73<i>b</i><sub>1</sub> ... <i>b</i><sub><i>k</i></sub>74... <i>b</i><sub><i>m</i></sub> <br>75 76<i>r</i><sub>1</sub> ... <i>r</i><sub><i>k</i></sub>77... <i>r</i><sub><i>n</i></sub> <br>78</blockquote>79</p>80 81 82 83<p>84The integers <i>m</i> and <i>n</i> are the number of blue cards85and that of red cards, respectively.86You may assume 1 &le; <i>m</i> &le; 500 and 1&le; <i>n</i> &le; 500.87 88<i>b</i><sub><i>k</i></sub> (1 &le; <i>k</i> &le; <i>m</i>) and89<i>r</i><sub><i>k</i></sub> (1 &le; <i>k</i> &le; <i>n</i>) are90numbers printed on the blue cards and the red cards respectively,91that are integers greater than or equal to 2 and less than 9210000000 (=10<sup>7</sup>). 93The input integers are separated by a space or a newline.94Each of <i>b</i><sub><i>m</i></sub> and <i>r</i><sub><i>n</i></sub> is95followed by a newline.96There are no other characters in the dataset.97 98</p>99 100 101 102 103<p>104The end of the input is indicated by a line containing two zeros105separated by a space.106</p>107 108 109 110<h3>Output</h3>111 112 113 114<p>115For each dataset, output a line containing an integer that indicates116the maximum of the number of the pairs. 117</p>118 119 120<h3>Sample Input</h3>121 122<pre>1234 31242 6 6 151252 3 51262 31274 91288 16 321294 21304 9 11 131315 71325 51332 3 5 1001 10011347 11 13 30 3013510 101362 3 5 7 9 11 13 15 17 291374 6 10 14 18 22 26 30 34 3813820 20139195 144 903 63 137 513 44 626 75 473140876 421 568 519 755 840 374 368 570 872141363 650 155 265 64 26 426 391 15 421142373 984 564 54 823 477 565 866 879 638143100 100144195 144 903 63 137 513 44 626 75 473145876 421 568 519 755 840 374 368 570 872146363 650 155 265 64 26 426 391 15 421147373 984 564 54 823 477 565 866 879 638148117 755 835 683 52 369 302 424 513 87014975 874 299 228 140 361 30 342 750 819150761 123 804 325 952 405 578 517 49 457151932 941 988 767 624 41 912 702 241 426152351 92 300 648 318 216 785 347 556 535153166 318 434 746 419 386 928 996 680 975154231 390 916 220 933 319 37 846 797 54155272 924 145 348 350 239 563 135 362 119156446 305 213 879 51 631 43 755 405 499157509 412 887 203 408 821 298 443 445 96158274 715 796 417 839 147 654 402 280 17159298 725 98 287 382 923 694 201 679 99160699 188 288 364 389 694 185 464 138 406161558 188 897 354 603 737 277 35 139 556162826 213 59 922 499 217 846 193 416 52516369 115 489 355 256 654 49 439 118 9611640 0165</pre>166 167 168<h3>Output for the Sample Input</h3>169 170 171<pre>172317311740175417691771817885179</pre>180 181 182