除法練習

題目敘述

Alice 跟 Bob 今天剛學到了除法跟質數的概念，他們知道一個數字是質數的意思就是那個數只有兩個因數，例如 $2, 3$ 都是質數，而 $1, 4$ 就不是質數。他們想要透過遊戲強加他們的反應，因此他們在桌子上寫下了 $N$ 個正整數，兩個人輪流選擇一個桌上的數字 $X_i$ ，再選擇一個可以整除那個數的質數 $p$，接著用那個質數 $p$ 去除 $X_i$。在同一回合中，只要還能夠整除，就可以除任意多次。沒有辦法動作的人就輸了。

舉個例子：一開始桌上有三個數字 $2,3,4$ ，Alice 選擇第三個數字 $X_3=4$ ，再選一個質數 $p=2$ ，接著用 $p$ 去除兩次，因此現在桌上的數字變成了 $2,3,1$。

一開始桌上有 $N$ 個數字，但是有一個數字被國防布蓋住了，因此只能看到其中的 $N-1$ 個數字，他們打算遊戲開始後再把布拿開，但已經知道那個數字不會大於 $M$ 。現在想要請問若 Alice 先開始，則有多少種狀況會使得 Bob 有必勝策略？

輸入說明

第一行有兩個正整數 $N, M$ 表示總共有 $N$ 個數字，被蓋住的數字不超過 $M$。 第二行有 $N-1$ 個正整數，代表沒有被蓋住的數字們，每個數字的大小不超過 $10^7$。

輸出說明

請輸出 Bob 有必勝策略的狀況數有幾種。

範例輸入1

3 3
1 2

範例輸出1

2

範例輸入2

4 3
4 3 1

範例輸出2

0

配分方法

• 30% $1 \leq N \leq 100$, $1 \leq M \leq 1000$
• 100% $1 \leq N \leq 10^6$, $1 \leq M \leq 10^7$

Hints

備註

Judge Setting