405701: GYM102051 B Nate and Bones

Nate loves dinosaurs very much due to the influence of the anime and card game Dinosaur King in his childhood. Recently, he has been collecting many variants of the new craze called "Fossilites," dinosaurs in bone/fossil form. He is very much in love with them and plays with them everyday, hence his nickname "Bones." One day, Nate discovered something horrible. While at school, his little brother played with his Fossilites! His younger brother took his dinosaurs apart and tried to fit the different bones to different bodies. His mom cleaned up the mess by just placing piles of bones into $$$n$$$ different boxes such that each box contains $$$m$$$ different bones.

Nate decides to focus on finding the bones of his favorite dinosaur first. Luckily, there is a way for Nate to identify them. His favorite dinosaur has weight $$$x$$$. A bone with length $$$l$$$ belongs to his favorite dinosaur if and only if $$$l$$$ and $$$x$$$ share a common factor besides $$$1$$$. That is to say, there exists an integer $$$d>1$$$ such that both $$$l$$$ and $$$x$$$ are divisible by $$$d$$$. He can get each bone and use math to help him out. He is not patient with numbers, however, so help Nate check if he is correct through a program.

Help Nate check if he got all the bones for the dinosaur by finding the total number of bones that belong to his favorite dinosaur.

The first line of input contains three space-separated integers $$$n$$$, $$$m$$$, and $$$x$$$, respectively. The first integer, $$$n$$$, is the number of boxes. The second integer, $$$m$$$, is the number of bones per box. The third integer, $$$x$$$, is the dinosaur's weight.

The next $$$n$$$ lines of input each contain $$$m$$$ space-separated integers corresponding to a bone's length $$$l_i$$$.

Constraints

$$$1 \leq n,m \leq 100$$$

$$$2 \leq l_i \leq 10^5$$$

$$$2 \leq x \leq 10^5$$$

Output a single integer, the total number of bones that belong to dinosaur $$$x$$$.

2 3 12
5 7 6
29 12 20

3

5 5 100
11 2 3 4 5
1000 2000 3000 4000 5000
21 1222 99 83 75
921 182 27 40 284
6474 301 734 1000 990

17

In the first case: the factors of $$$12$$$ are $$$1,2,3,4,6,12$$$. In the first box, only $$$6$$$ is divisible by one of those other than $$$1$$$. In the second box, both $$$12$$$ and $$$20$$$ are divisible by one of the factors. The total number of correct bones is $$$3$$$.

In the second case: the factors of $$$100$$$ are $$$1,2,4,5,10,20,25,50,100$$$. In the first box, $$$2$$$, $$$4$$$, and $$$5$$$ are divisible by a factor of $$$100$$$. In the second box, all numbers are divisible. In the third box, $$$1222$$$ and $$$75$$$ are divisible. In the fourth box, $$$182$$$, $$$40$$$, $$$284$$$ are divisible. In the fifth and last box, all numbers apart from $$$301$$$ are divisible. The total number of correct bones is $$$17$$$.