Humam (AKA Homam) goes fishing to put food on the table. One day, while using his fishing rod, he caught a bottle instead of a fish. Inside the bottle, he found a treasure map, and he was thrilled to discover the hidden treasure, leading him to stop fishing forever after.
He took his friend, Wael, saddled their horses, and went to the castle where the treasure was buried. They spent a week deciphering the riddles that led to the exact location of the treasure. Once they did, they started digging until they finally found the treasure, a buried array!
Both disappointed that the treasure was not money, gold or any valuable items, they started packing their things to head home. While doing so, Humam thought that he would take the array with him as a remembrance of this journey. Wael, not really caring about taking the array or leaving it, said: "Eh seedie, hot bel kherej". The kherej of Humam's horse was so small to fit the whole array, so he wanted to take a subset of its elements.
Humam thinks that a set of integer numbers is $$$\textit{good}$$$ if their product is divisible by $$$x$$$, where $$$x$$$ is Humam's lucky number.
Humam and Wael wanted to head home before it's dark. They want to find the minimum size of a subset of the buried array where it is $$$\textit{good}$$$. Can you help them?
a subset of an array $$$a$$$ is an array $$$b$$$ that can be obtained by removing zero or more elements from $$$a$$$.
The first line of the input contains two space-separated integer numbers $$$n$$$ and $$$x$$$ $$$(1 \le n \le 2\times 10^6, 1 \le x \le 10^9)$$$. The size of the buried array and Humam's lucky number, respectively.
The second line contains $$$n$$$ space-separated integer numbers $$$a_1, a_2 \dots a_n$$$ $$$(1 \le a_i \le 10^{18})$$$, where $$$a_i$$$ is the $$$i-th$$$ integer number in the buried array.
As the input file is large, consider using fast I/O
Print a single integer number. The minimum size of a subset of the buried array where it is $$$\textit{good}$$$, or $$$-1$$$ if there is no such subset.
3 9 15 48 3
2
5 20 6 15 2 2 14
3
