akinyan's favorite numbers

2 secs 1024 MB
akinyan

問題文


akinyan君の好きな数を次のように定めます.

  • ( の倍数かつ の倍数)ではない の倍数か の倍数

例えば のとき, akinyan君は などは好きですが, などは好きではありません.

長さ の数列 と正整数 が与えられるので以下の条件を満たす個数を答えてください.

  • は akinyan 君が好きな数である. ()

制約


  • 入力は全て整数

入力


入力は以下の形式で標準入力から与えられます.


出力


答えを出力してください.

サンプル


入力1
4 2 3
2 3 5 4
出力1
5

条件を満たすのは,
のときで,
のときで,
のときで,
のときで,
のときで,
の5通りです.

入力2
10 509 2009
1 1 2 3 5 8 13 21 34 55
出力2
0

答えが0になる場合もあります.

提出


Go (1.14)