P20535 [HackerEarth] Chandu is a big fan of primes. He defines another kind of primes alpha-primes. Alpha-primes are defined as primes for which there exists some suffix of a given number which is a prime. F
普及-
题目描述

Chandu is a big fan of primes. He defines another kind of primes alpha-primes. Alpha-primes are defined as primes for which there exists some suffix of a given number which is a prime. For example, 12 is not prime but 12 is alpha prime as there exists a suffix which is a prime. In case of 12, 2 is prime therefore 12 is alpha-prime.
Now, he gives you Q queries of the form L R for which you have to calculate how many alpha-primes are there in the range [L, R].

Input :
First line contains a single integer Q denoting no. of queries.
Next Q line contains two space separated integers L and R.

Output :
For each query output the count of alpha-primes in the range [L, R]

Constraints :
1 ≤ Q ≤ 10^6
1 ≤ L ≤ R ≤ 10^6

SAMPLE INPUT
4
1 2
10 14
110 114
5 5

SAMPLE OUTPUT
1
3
3
1

Explanation

Query 1 2
1 is neither prime nor alpha-prime.
2 is prime and there exists a suffix which is 2 itself which is prime therefore 2 is alpha-prime.
Therefore total count in range 1 2 is 1.
Query 10 14
10 is not aplha-prime as its suffix 0 and 10 are not prime.
11 is alpha-prime as its suffix 11 is prime.
12 is alpha-prime as its suffix 2 is prime.
13 is alpha-prime as its suffix 3 is prime.
14 is not alpha-prime as its suffix 4 and 14 are not prime.
Therefore total count in range 10 14 is 3.

输入格式

见题面

输出格式

见题面

样例输入
10 1 2 1 6 8 10 5 6 1 7 4 6 2 6 7 8 5 7 1 2
样例输出
169 265 464 7 36 189 333 10 138 62 171 332 183 276 35 439 171 261 85 291 90 260 344 70 110 185 461 317 471 439 259 149 191 177 31 177 212 198 142 309 7 446 267 177 270 85 260 120 69 205 56 64 263 289 192 85 175 90 39 117 20 31 142 148 162 386 9 352 288 184 195 126 85 290 226 82 249 98 52 256 132 64 105 351 25 64 294 60 256 107 167 146 50 72 103 514 142 154 266 295 179 14 417 414 204 257 23 105 262 26 329 331 153 367 357 507 1 99 67 348 61 301 113 208 96 160 8 349 3 59 49 343 110 110 253 291 204 235 121 203 90 61 351 292 52 170 514 231 130 122 291 37 4 268 251 518 91 108 239 87 59 358 53 87 130 109 26 72 54 104 275 356 15 92 118 320 108 165 70 328 133 36 45 168 106 173 59 18 114 44 83 290 310 284 322 32 287 33 166 319 271 127 24 137 57 21 269 322 106 129 35 115 172 43 226 107 345 255 358 10 57 128 495 175 269 201 395 43 200 137 6 213 124 128 309 338 119 83 272 288 44 251 68 237 201 106 71 204 159 226 94 142 136 1 61 411 269 6 317 126 423 357 420 311 177 129 287 401 243 93 77 329 464 134 36 167 35 129 135 104 459 391 295 302 115 297 57 398 73 67 280 26 271 265 460 17 9 206 281 205 174 246 170 213 366 179 247 198 281 190 76 40 13 190 330 48 426 74 80 32 301 165 20 82 48 75 422 97 207 183 434 258 141 43 115 185 335 71 406 43 237 349 419 153 377 395 379 327 94 11 279 60 29 357 164 60 158 191 9 407 230 277 247 389 158 11 168 324 39 100 157 180 17 161 25 378 36 100 393 254 127 390 105 242 104 172 100 158 186 228 31 88 62 378 91 147 73 194 228 369 314 105 19 255 405 16 204 151 94 366 74 407 83 122 130 77 96 120 225 129 133 245 112 44 242 190 83 166 310 143 233 262 308 333 329 353 70 109 41 56 169 84 310 268 17 180 487 27 77 64 420 132 259 258 19 344 31 113 32 279 306 103 171 12 366 239 286 384 315 80 343 282 36 48 118 264 70 185 320 192 334 245 63 325 94 5 325 17 408 322 38 146 102 204 12 188 101 214 274 61 179 238 340 111 418 142 46 465 204 62 398 114 258 3 21 318 67 54 464 148 55 204 14 333 284 44 38 278 202 84 157 121 120 8 291 3 335 165 333 323 87 103 148 223 119 220 177 170 314 150 148 215 52 97 323 93 150 304 323 247 308 224 69 116 383 74 188 53 390 287 26 59 5 281 103 166 185 144 243 373 124 24 12 9 119 38 141 107 87 68 332 14 82 97 357 125 36 288 310 96 243 16 156 393 107 110 149 68 90 14 109 143 261 158 182 294 118 77 19 377 118 29 124 471 265 234 168 162 266 37 187 211 6 127 104 402 92 17 271 62 174 50 199 247 111 174 274 219 19 88 60 73 139 296 175 120 133 399 22 205 132 15 27 132 91 253 164 469 285 17 84 306 145 340 232 140 6 302 136 40 58 284 200 140 132 404 250 268 326 30 313 2 242 247 36 130 89 75 37 49 325 30 265 118 370 209 36 107 284 42 77 433 39 41 121 7 107 62 13 310 378 28 168 157 68 387 75 61 135 126 26 383 82 314 109 121 373 142 376 91 312 111 97 12 193 242 443 194 365 117 68 212 512 393 236 139 11 246 341 50 236 327 29 162 492 210 508 311 69 84 91 176 79 365 325 279 171 165 236 138 64 12 345 25 407 254 171 129 226 357 360 65 20 362 117 50 69 401 67 367 15 433 25 63 5 150 36 194 121 315 198 216 141 6 76 239 100 125 112 365 6 53 195 44 274 147 261 206 177 286 356 360 266 6 163 142 157 303 154 120 12 57 208 414 85 291 278 13 150 174 172 105 135 61 224 356 214 231 47 355 310 221 237 372 297 161 27 254 215 292 292 288 63 70 145 236 152 54 153 74 218 71 5 243 209 456 102 149 278 116 183 32 123 430 39 72 217 76 136 311 227 152 193 193 24 59 42 190 364 51 354 193 26 57 392 501 434 342 405 129 226 351 23 270 16 368 58 327 482 33 337 110 99 341 324 364 353 95 208 319 333 13 29 195 234 1 239 70 167 297 148 38 112 44 68 162 228 137 131 82 22 311 159 173 61 267 133 1 282 54 41 21 88 263 246 70 75 287 104 176 140 167 129 246 473 320 78 244 149 285 179 114 113 289 413 349 23 196 54 20