NGM2 - Another Game With Numbers

Little Chikoo likes to play with numbers. Often he plays the following game:

  1. He chooses a number N and a set of positive integers.
  2. He writes down all the numbers from 1 to N.
  3. He chooses the first number (say x) from the set and cancels out all the multiples of x from 1 to N, including x.
  4. He repeats step 3 for all the numbers from the set.

One day Little Chikoo was in a mood to play pranks. So his brother asked him to play the game with a certain challenge. He made the game a little harder and asked him to find out the number of integers which aren't cancelled after he completes step 4. If he does that then Little Chikoo gets to play on his brother's Nintendo for one full day. Now Little Chikoo is in a hurry and wants to finish the job as soon as possible. He has asked for your help.

Input

The first line of the input contains N and K. (N <= 10^9, K <= 15)

Then K numbers follow all in a single line. All numbers are <= 100.

Output

The output file must contain the number of integers that aren't cancelled after he finishes step 4 of the game.

Example

Input:
10 3
2 4 5

Output:
4

(The numbers 1, 3, 7 and 9 weren't cancelled).


Added by:Paranoid Android
Date:2010-03-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:-

hide comments
2019-03-31 14:06:59
where is segment tree in this problem? @linkret
2019-03-27 16:43:03
such intrinsically good solution of this!
2018-12-25 14:12:40
use long long int to clear the last test case!
2018-07-19 15:36:29 Rahul Jain
Nintendo... no wonder question is from 2010 :D
2017-12-28 13:25:38
use long long int, otherwise last test case will give wrong answer.
2017-07-27 09:52:40
WA on test case 25!!!anyone help plz??
2017-03-26 16:35:45
tle at test case 25:-(
2017-02-21 21:04:57
Very Easy problem !! Just do Inclusion-exclusion !! :)
2016-12-27 06:55:18
read about bitmasking on codeforces
2016-10-02 12:10:58 hacker_sk
lol, due to int .. i got 2 wrong ans in 25th(last) test case. finally AC. :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.