| 问题描述 |
|---|
easy version 和 hard version 的区别仅在于数据范围和回答的内容。 越越有 n 个数字，涂涂希望考察越越对自己数字的理解能力，所以会询问越越 q 次，涂涂每次询问一个数字 m，越越需要回答自己的 n 个数字中与 m 不互质的数字有多少个。 |
| 输入描述 |
第一行是一个正整数 n 代表越越拥有的数字个数。(1 ≤ n ≤ 1e5) 然后是 n 个数字，对于每个数字 x，都有 1 ≤ x ≤ 1e5。 接下来是一个正整数 q 代表询问的次数。(1 ≤ q ≤ 2000) 最后是 q 个正整数，对于每个数字 m 都有 1 ≤ m ≤ 1e5。 |
| 输出描述 |
针对每组案例，输出越越有多少个数字与涂涂给出的数字不互质，然后换行。 |
| 样例输入复制样例 |
5 1 2 3 4 5 2 7 5 |
| 样例输出 |
0 1 |
| 相关 |