Background

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

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

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

$$gcd(ai,k)= 1$$

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

Input

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

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

Output

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

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

Samples

3 12
6 1 5

3
1
7
11

3 20
3 5 8

6
1
7
11
13
17
19

Limitation

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

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

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

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