It is now the school holidays and Little Joseph wants to play MapleStory.
However, his mum, fearing for his academic performance, insists that he knows the multiplication table first, in preparation for his exams next year.
[Woah so kiasu].
Little Joseph, being playful, wanted to give his mum a hard time. As such, when his mum tests him on multiples of n, he writes k numbers which he claims are all multiples of n, just to prove that he knows his stuff.
Little Joseph's mum, seeing the long numbers Little Joseph has wrote, decided to enlist your help in checking the answers.
Being confused, you decided to check up on divisiblity rules and obtained the following rules:
- All whole numbers are multiples of 1
- A number would be a multiple of 2 if the last digit of the number is either 0, 2, 4, 6 or 8.
- A number would be a multiple of 3 if the sum of its digits is a multiple of 3.
- A number would be a multiple of 4 if the last 2 digits is divisible by 4.
- A number would be a multiple of 5 if the last digit of the number is either 0 or 5.
- A number would be a multiple of 6 if its a multiple of both 2 and 3.
- A number would be a multiple of 7 if adding 5 times the last digit to the rest would result in a number still divisible by 7.
Doing this method with 49 will result back with 49, all other multiples of 7 would result in a different number.
- A number would be a multiple of 8 if the last 3 digits is divisible by 8.
- A number would be a multiple of 9 if the sum of its digits is a multiple of 9.
- A number would be a multiple of 10 if the last digit is 0.
Input
The first line of input consists of 2 integers, n followed by k
The following k line consists of 1 integer each, these are the numbers Little Joseph thinks are the multiples of n.
Output
Output an integer to indicate how many numbers has Little Joseph got correct. (Refer to Sample Output)
Problem Limits
For 50% of the testcases, 1 <= k <= 100 and 1020 < ki < 10100
For 100% of the testcases 1 <= k <= 1000 and 1020 < ki < 101000
For 100% of the testcases, 1 <= n <= 10
33% of the marks are allocated to when n=7
Sample Input 1
5 7
82736848236482738345
438477592838483847534
85479839577695743740
8753402893478264659842
84728856837472639480
8343228031857833829746
18273758192937659285
Sample Output 1
4
Explanation for Sample Output 1
82736848236482738345, 85479839577695743740, 84728856837472639480, 18273758192937659285 are multiples of 5 as they end with 0 or 5 while the rest are not.
Sample Input 2
7 1
201240079862147084444
Sample Output 2
1
Explanation for Sample Output 2
201240079862147084444: 20124007986214708444 + 5*4 = 20124007986214708464
20124007986214708464: 2012400798621470846 + 5*4 = 2012400798621470866
2012400798621470866: 201240079862147086 + 5*6 = 201240079862147116
201240079862147116: 20124007986214711 + 5*6 = 20124007986214741
20124007986214741: 2012400798621474 + 5*1 = 2012400798621479
2012400798621479: 201240079862147 + 5*9 = 201240079862192
201240079862192: 20124007986219 + 5*2 = 20124007986229
20124007986229: 2012400798622 + 5*9 = 2012400798667
2012400798667: 201240079866 + 5*7 = 201240079901
201240079901: 20124007990 + 5*1 = 20124007995
20124007995: 2012400799 + 5*5 = 2012400824
2012400824: 201240082 + 5*4 = 201240102
201240102: 20124010 + 5*2 = 20124020
20124020: 2012402 + 5*0 = 2012402
2012402: 201240 + 5*2 = 201250
201250: 20125 + 5*0 = 20125
20125: 2012 + 5*5 = 2037
2037: 203 + 5*7 = 238
238: 23 + 5*8 = 63
63: 6 + 5*3 = 21
21: 2 + 5*1 = 7 (7 is a multiple of 7)
Therefore, 201240079862147084444 is a multiple of 7.