桌子上现在有m张蓝色卡片和n张红色卡片,每张卡片上有一个大于1的整数.现在你要从桌子上拿走一些卡片,分若干次拿.每次只能拿走一组卡片:这组卡片颜色不同,并且两张卡片上面的数字的最大公约数大于1.问:最多可以从桌上拿走多少组卡片.
每个输入文件中包含多组测试数据,每个文件中测试数据的数目不超过100. 文件的第一行读入一个整数T,为数据组数. 每组数据的格式如下: m n b1 b2 ... bm r1 r2 ... rn 第二行给出每张蓝色卡片上面的数字,第三行给出每张红色卡片上的数字.
对每组测试数据,输出最多可以拿走多少张卡片.
对100%的数据:1<=t<=100; 1<=mn<=500; 卡片上的数字大于1,小于10 000 000.