#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

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 10^{20} < *k _{i}* < 10

^{100}

For 100% of the testcases 1 <=

*k*<= 1000 and 10

^{20}<

*k*< 10

_{i}^{1000}

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.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 0 | 2 | 1s | 64MB | Average |

2 | 100 | 30 | 1s | 64MB | Average |

### Judge Compile Command

g++ ans.cpp -o multitable -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512