using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("4 3");
WillReturn.Add("2 6 6 15");
WillReturn.Add("2 3 5");
WillReturn.Add("2 3");
WillReturn.Add("4 9");
WillReturn.Add("8 16 32");
WillReturn.Add("4 2");
WillReturn.Add("4 9 11 13");
WillReturn.Add("5 7");
WillReturn.Add("5 5");
WillReturn.Add("2 3 5 1001 1001");
WillReturn.Add("7 11 13 30 30");
WillReturn.Add("10 10");
WillReturn.Add("2 3 5 7 9 11 13 15 17 29");
WillReturn.Add("4 6 10 14 18 22 26 30 34 38");
WillReturn.Add("20 20");
WillReturn.Add("195 144 903 63 137 513 44 626 75 473");
WillReturn.Add("876 421 568 519 755 840 374 368 570 872");
WillReturn.Add("363 650 155 265 64 26 426 391 15 421");
WillReturn.Add("373 984 564 54 823 477 565 866 879 638");
WillReturn.Add("100 100");
WillReturn.Add("195 144 903 63 137 513 44 626 75 473");
WillReturn.Add("876 421 568 519 755 840 374 368 570 872");
WillReturn.Add("363 650 155 265 64 26 426 391 15 421");
WillReturn.Add("373 984 564 54 823 477 565 866 879 638");
WillReturn.Add("117 755 835 683 52 369 302 424 513 870");
WillReturn.Add("75 874 299 228 140 361 30 342 750 819");
WillReturn.Add("761 123 804 325 952 405 578 517 49 457");
WillReturn.Add("932 941 988 767 624 41 912 702 241 426");
WillReturn.Add("351 92 300 648 318 216 785 347 556 535");
WillReturn.Add("166 318 434 746 419 386 928 996 680 975");
WillReturn.Add("231 390 916 220 933 319 37 846 797 54");
WillReturn.Add("272 924 145 348 350 239 563 135 362 119");
WillReturn.Add("446 305 213 879 51 631 43 755 405 499");
WillReturn.Add("509 412 887 203 408 821 298 443 445 96");
WillReturn.Add("274 715 796 417 839 147 654 402 280 17");
WillReturn.Add("298 725 98 287 382 923 694 201 679 99");
WillReturn.Add("699 188 288 364 389 694 185 464 138 406");
WillReturn.Add("558 188 897 354 603 737 277 35 139 556");
WillReturn.Add("826 213 59 922 499 217 846 193 416 525");
WillReturn.Add("69 115 489 355 256 654 49 439 118 961");
WillReturn.Add("0 0");
//3
//1
//0
//4
//9
//18
//85
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static long mX; // Xの頂点数
static long mY; // Yの頂点数
static long mSourceNode;
static long mSinkNode;
static long UB;
// 隣接行列で枝を表現
static long[,] mCapacityArr;
static long[,] mFlowArr;
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
long RestB = 0;
long RestR = 0;
var BList = new List<long>();
var RList = new List<long>();
foreach (string EachStr in InputList) {
SplitAct(EachStr);
if (RestB == 0 && RestR == 0) {
RestB = wkArr[0];
RestR = wkArr[1];
if (RestB == 0) break;
continue;
}
if (RestB > 0) {
long[] ReadArr = EachStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
BList.AddRange(ReadArr);
RestB -= ReadArr.Length;
continue;
}
if (RestR > 0) {
long[] ReadArr = EachStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
RList.AddRange(ReadArr);
RestR -= ReadArr.Length;
if (RestR == 0) {
Solve(BList.ToArray(), RList.ToArray());
BList.Clear();
RList.Clear();
}
}
}
}
static void Solve(long[] pBArr, long[] pRArr)
{
mX = pBArr.Length;
mY = pRArr.Length;
mSourceNode = mX + mY;
mSinkNode = mSourceNode + 1;
UB = mSinkNode;
mCapacityArr = new long[UB + 1, UB + 1];
mFlowArr = new long[UB + 1, UB + 1];
for (int I = 0; I <= pBArr.GetUpperBound(0); I++) {
for (int J = 0; J <= pRArr.GetUpperBound(0); J++) {
if (DeriveGCD(pBArr[I], pRArr[J]) > 1) {
mCapacityArr[I, mX + J] = 1;
}
}
}
for (long I = 0; I <= mX - 1; I++) {
mCapacityArr[mSourceNode, I] = 1;
}
for (long I = mX; I <= mX + mY - 1; I++) {
mCapacityArr[I, mSinkNode] = 1;
}
// フォード・ファルカーソンで解く
FordFulkerson();
}
// ユークリッドの互除法で2数の最大公約数を求める
static long DeriveGCD(long pVal1, long pVal2)
{
long WarareruKazu = pVal2;
long WaruKazu = pVal1;
while (true) {
long Amari = WarareruKazu % WaruKazu;
if (Amari == 0) return WaruKazu;
WarareruKazu = WaruKazu;
WaruKazu = Amari;
}
}
static void FordFulkerson()
{
while (true) {
List<long> NodeList = ExecDFS();
if (NodeList == null) break;
//Console.WriteLine("経路を発見しました");
//NodeList.ForEach(pX => Console.Write("{0},", pX));
//Console.WriteLine();
// 経路に流す量
long CurrFlow = long.MaxValue;
for (int I = 0; I <= NodeList.Count - 2; I++) {
long FromNode = NodeList[I];
long ToNode = NodeList[I + 1];
CurrFlow = Math.Min(CurrFlow, mCapacityArr[FromNode, ToNode]);
}
//Console.WriteLine("この経路に{0}の水を流します", CurrFlow);
for (int I = 0; I <= NodeList.Count - 2; I++) {
long FromNode = NodeList[I];
long ToNode = NodeList[I + 1];
mCapacityArr[FromNode, ToNode] -= CurrFlow;
mFlowArr[FromNode, ToNode] += CurrFlow;
// 逆辺を追加する
mCapacityArr[ToNode, FromNode] += CurrFlow;
}
}
long Answer = 0;
for (long I = 0; I <= UB; I++) {
Answer += mFlowArr[I, UB];
}
Console.WriteLine(Answer);
}
struct JyoutaiDef
{
internal long CurrNode;
internal List<long> NodeList;
}
// 深さ優先探索を行い、始点から終点へのノードのListを返す
// なければnullを返す
static List<long> ExecDFS()
{
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPish;
WillPish.CurrNode = mSourceNode; // 始点のノードはmSourceNode
WillPish.NodeList = new List<long>();
WillPish.NodeList.Add(WillPish.CurrNode);
Stk.Push(WillPish);
// DFSを繰り返すので、レベルの低い訪問を優先しても問題ない
var VisitedSet = new HashSet<long>();
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
// 終点のノードはmSinkNode
if (Popped.CurrNode == mSinkNode) {
return Popped.NodeList;
}
for (long I = 0; I <= UB; I++) {
long CurrCapacity = mCapacityArr[Popped.CurrNode, I];
if (CurrCapacity == 0) continue;
if (VisitedSet.Add(I) == false) continue;
WillPish.CurrNode = I;
WillPish.NodeList = new List<long>(Popped.NodeList) { I };
Stk.Push(WillPish);
}
}
return null;
}
}