{"raw_statement":[{"iden":"problem statement","content":"We say that a odd number $N$ is _similar to 2017_ when both $N$ and $(N+1)/2$ are prime.\nYou are given $Q$ queries.\nIn the $i$\\-th query, given two odd numbers $l_i$ and $r_i$, find the number of odd numbers $x$ similar to 2017 such that $l_i ≤ x ≤ r_i$."},{"iden":"constraints","content":"*   $1≤Q≤10^5$\n*   $1≤l_i≤r_i≤10^5$\n*   $l_i$ and $r_i$ are odd.\n*   All input values are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$Q$\n$l_1$ $r_1$\n$:$\n$l_Q$ $r_Q$"},{"iden":"sample input 1","content":"1\n3 7"},{"iden":"sample output 1","content":"2\n\n*   $3$ is similar to 2017, since both $3$ and $(3+1)/2=2$ are prime.\n*   $5$ is similar to 2017, since both $5$ and $(5+1)/2=3$ are prime.\n*   $7$ is not similar to 2017, since $(7+1)/2=4$ is not prime, although $7$ is prime.\n\nThus, the response to the first query should be $2$."},{"iden":"sample input 2","content":"4\n13 13\n7 11\n7 11\n2017 2017"},{"iden":"sample output 2","content":"1\n0\n0\n1\n\nNote that $2017$ is also similar to 2017."},{"iden":"sample input 3","content":"6\n1 53\n13 91\n37 55\n19 51\n73 91\n13 49"},{"iden":"sample output 3","content":"4\n4\n1\n1\n1\n2"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}