{"raw_statement":[{"iden":"statement","content":"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.\n\nNate 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.\n\nHelp Nate check if he got all the bones for the dinosaur by finding the total number of bones that belong to his favorite dinosaur.\n\nThe 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. \n\nThe next $n$ lines of input each contain $m$ space-separated integers corresponding to a bone's length $l_i$.\n\n*Constraints*\n\n$1 <= n, m <= 100$\n\n $2 <= l_i <= 10^5$\n\n $2 <= x <= 10^5$\n\nOutput a single integer, the total number of bones that belong to dinosaur $x$.\n\nIn 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$.\n\nIn 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$. \n\n"},{"iden":"input","content":"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 <= n, m <= 100$ $2 <= l_i <= 10^5$ $2 <= x <= 10^5$"},{"iden":"output","content":"Output a single integer, the total number of bones that belong to dinosaur $x$."},{"iden":"examples","content":"Input2 3 125 7 629 12 20Output3Input5 5 10011 2 3 4 51000 2000 3000 4000 500021 1222 99 83 75921 182 27 40 2846474 301 734 1000 990Output17"},{"iden":"note","content":"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$. "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, and let $ S_n $ be the symmetric group on $ n $ elements (i.e., the set of all permutations of $ [1, n] $).  \nA segment $ [L, R] \\subseteq [1, n] $ is *consecutive* in a permutation $ p \\in S_n $ if there do not exist indices $ x, y, z \\in [1, n] $ such that:  \n- $ x < z \\in [L, R] $,  \n- $ y \\notin [L, R] $,  \n- $ p_x < p_y < p_z $.  \n\nLet $ f(n) $ denote the minimum number of permutations Rikka must choose such that for every $ p \\in S_n $, there exists a chosen permutation $ q $ with identical consecutive-segment responses to all queries $ [L, R] $.\n\n**Constraints**  \n- $ 1 \\leq N \\leq 5000 $  \n- $ P $ is a prime such that $ P = k \\cdot 2^{14} + 1 $ for some $ k \\in \\mathbb{N} $, and $ 1 \\leq P < 2^{30} $\n\n**Objective**  \nFor each $ n = 1, 2, \\dots, N $, compute $ f(n) \\mod P $.","simple_statement":"For each n from 1 to N, output the minimum number of permutations Rikka must choose so that, based on consecutive-segment queries, she can uniquely identify LCR’s hidden permutation. Answer modulo P.","has_page_source":false}