题目描述

小明总是陶醉在数论的海洋里，他知道：数论是数学的皇后。而数论的核心，就是质数！

但是现在小明想研究互质问题，$a$ 和 $b$ 互质，即 $2$ 个数的最大公约数是 $1$，表示为 $gcd(a,b)=1$。

现在，有 $N$ 个正整数，从 $a_1$ 到 $a_n$，你要找出在 $1$ 到 $M$ 之间，有多少个整数 $k$ 能够满足对于任意 $a_i$，都有:

小明觉得这是一个很神奇的东东，他有点不会做。他希望有一个数论高手可以来帮助他，你是小明心目中的数论高手么？来解决这个问题吧!

输入格式

输入的第一行是 $2$ 个正整数 $N$ 和 $M$。

输入的第二行是 $N$ 个正整数 $a_1, a_2, ..., a_N$，空格隔开。

输出格式

3 12
6 1 5

3
1
7
11

3 20
3 5 8

6
1
7
11
13
17
19

数据范围

对于所有的数据，保证 $1<=N<=10^5，1<=M<=10^6，1<=ai<=10^6$

其中 $30\%$ 的数据，$N,M,a_i$ 均 $<=10^3$

其中 $30\%$ 的数据，$N<=10^3$，$M,ai<=10^6$

其中 $40\%$ 的数据，$N<=10^5$，$M,ai<=10^6$