P20612 [HackerEarth] Smith numbers were named by Albert Wilansky of Lehigh University. He noticed the property in the phone number (493-7775) of his brother-in-law Harold Smith:
普及
题目描述

Smith numbers were named by Albert Wilansky of Lehigh University. He noticed the property in the phone number (493-7775) of his brother-in-law Harold Smith:
4937775 = 3 × 5 × 5 × 65837 and (4 + 9 + 3 + 7 + 7 + 7 + 5) = (3)+ (5) + (5) + (6 + 5 + 8 + 3 + 7) = 42.
In simple words, a number is said to be a Smith Number if its digit_sum is equal to the sum of digit_sums_of_all_its_prime_factors.

Input:
First line contains T which is the number of test cases.
T lines follow each containing two integers L and R.

Output:
For each range L to R (both inclusive), output the number of Smith Numbers in this range.

Constraints:

1 ≤ T ≤ 10^6
2 ≤ L ≤ R ≤ 10^7

Scoring:

1 ≤ T ≤ 1000, 2 ≤ L ≤ R ≤ 10000: (30 pts)
Orginal Constraints : (70 pts)

Note:
Large IO. Use scanf/printf(in C/C++).

SAMPLE INPUT
2
2 3
2 10

SAMPLE OUTPUT
2
5

Explanation

Case 1: In the range 2 to 3, both the numbers are Smith Numbers. As both have just one prime factor, the digitSum thus will be same.
Hence answer is 2.

Case 2: 2,3,4,5,7 are the Smith Numbers in this range. 4 is a Smith Number because 4=2*2 and dgtSum(4)=dgtSum(2)+dgtSum(2). So the answer for this case is 5.

输入格式

见题面

输出格式

见题面

样例输入
1000 3401 7233 1336 3749 9029 9422 2876 8237 8226 9126 8743 9829 7761 8791 7502 9483 3406 3637 5801 7304 5054 5473 3153 4890 2744 8318 4656 7392 4884 6309 8220 8500 8235 8924 1544 7861 1050 3749 9256 9965 2307 7793 1017 9808 3264 4250 7128 8628 5590 6648 2937 4242 1560 8925 9789 9891 6268 7845 2120 8603 2260 5683 5549 7229 8219 8386 3529 9848 9972 9984 663 6022 1923 4995 6252 7911 9590 9775 6934 8378 6334 7744 3515 5662 6472 8892 4733 4996 5224 5548 7623 8688 6035 7836 5414 6278 8926 9556 6000 6267 2735 5970 3130 8086 1036 1659 2632 6421 3388 3537 3754 6842 641 3154 3384 4576 4345 5271 2121 6798 8301 9657 7330 9776 3009 3778 3594 5869 4784 4869 9171 9764 428 3853 6127 6533 8606 9341 9842 9846 5464 7727 7857 9082 1280 1978 9897 9950 3893 8432 5671 7829 273 4022 1682 9789 765 9213 9304 9800 5221 9679 7536 9736 9385 9636 5932 7324 5224 8168 9079 9576 6323 9014 1860 6001 2651 7829 6373 8887 756 3123 2533 9028 4770 5315 2625 8071 5501 7493 5793 9100 5748 7281 8779 9277 1784 5332 3942 9998 2018 3140 272 3015 3398 5426 7957 8341 1380 5286 7633 9415 4731 5160 1122 1709 423 8735 2527 5261 343 9120 9744 10000 5193 8887 2092 5174 583 3239 4988 6023 7888 7917 6540 8093 1050 5021 1781 4034 2949 9172 9 6254 5313 8971 8828 9969 6403 9885 9120 9245 885 3116 7420 7447 2923 7082 942 6005 4585 5379 5166 5991 7822 9539 3598 7381 566 827 5763 6948 3383 6493 8563 9807 1699 3093 7082 8421 738 6039 2242 6196 4109 7947 2974 8867 8848 8883 1990 8881 7836 7898 9547 10000 7346 8012 4806 8175 7390 9596 236 6751 2021 8257 7097 9524 4468 5507 743 5261 1998 8797 4321 8273 9465 9467 5678 8618 8963 9798 6173 8948 2994 5268 4470 7685 5301 5375 7806 9516 9439 9627 645 3230 3199 6842 916 4510 9440 9627 8707 9217 3753 7258 3750 4663 7790 9780 7158 8308 7033 9132 395 6679 7957 8306 9704 9795 1070 6120 4514 5238 8783 9585 7561 9918 2882 6049 1288 4413 1054 1072 3308 9023 3970 5764 4887 8379 5162 7667 1385 5137 138 7762 3062 5434 2013 3945 7371 9224 7349 9133 7268 9066 4421 8484 6673 8100 4806 5967 988 1783 6213 7831 1996 5267 74 893 9135 9341 6271 9588 5765 9912 4210 7379 4089 7222 6914 7021 4711 5606 7377 9162 5456 5719 5050 8798 3249 4061 3248 3491 7069 7391 5979 6434 9029 9622 1116 6695 8322 9781 1051 2857 1742 2151 7413 7884 9352 9641 8573 8618 1313 4871 478 7345 4427 6238 6297 8684 3218 8149 1342 5853 9777 9783 1115 5826 9329 9374 6691 8354 1323 7589 5276 7439 1419 6650 3995 9934 9009 9377 9830 9884 4660 6015 3743 3799 3810 9368 7943 9941 4862 6259 7218 7636 864 1176 2079 9538 2939 9795 4164 5543 2975 9015 5508 6002 9252 9837 4288 5990 9176 9184 452 2089 4582 7775 352 1972 3655 5920 6699 7314 1580 8435 2326 9243 6356 8864 7946 8667 2249 6965 4212 8240 9622 9665 6919 9986 359 2627 3623 4411 7479 8590 2674 9540 6031 7896 1253 3625 6600 8637 1744 9480 9121 9754 6965 8205 2704 5824 3032 9150 2000 9690 6369 9643 9118 9235 4383 8689 6662 8465 6188 8758 278 9361 4577 8677 1850 2458 3481 6855 165 3691 3642 4085 1129 3559 897 5332 3406 7305 3036 9407 367 4615 2399 4288 2504 4692 9698 9976 7979 9995 3940 7837 2666 8132 2255 9758 1690 4062 7382 9223 7231 8907 5429 5537 9134 9739 1048 9686 696 3180 8901 9355 9558 9933 5690 5940 643 8921 8822 9631 9246 9994 4923 7842 1244 4422 3184 8120 1405 9637 8304 8563 8329 9538 1527 5635 8707 8798 6575 8913 5541 9017 183 5695 2451 4106 4630 5929 2048 5887 182 9522 7748 9838 2180 4401 1348 3746 7313 9406 8116 9659 448 5751 5498 5867 8824 9980 8849 8928 9950 9983 7645 9731 6137 8423 7035 8866 923 7636 2281 8845 9131 9828 1435 7980 379 3550 9819 9994 5975 8824 7919 9159 5787 9521 7821 9255 5598 8466 914 6634 6955 7270 8216 8246 5716 9405 3656 6204 2354 5591 5637 7086 2411 4430 7833 9910 9187 9676 2236 9628 202 207 8174 8441 5152 9689 7577 8528 5366 8528 8601 9506 9460 9470 4429 4916 2032 6293 7775 7954 7253 7849 7920 9507 6458 9079 6817 7073 4363 6848 137 8587 724 1326 9678 9747 7140 8347 5781 6214 3030 3901 6277 9063 4331 9969 503 5494 664 7192 9979 9984 4490 5229 897 905 184 5554 8928 9127 2198 3758 2110 4400 9658 9849 5574 8994 8124 8462 494 676 420 8533 7883 9849 4521 9404 1081 8692 5806 8246 3200 4107 6251 7999 7838 9032 6651 7690 7054 9297 9531 9616 7167 7830 8820 8839 4128 4718 3330 8235 7425 7896 9065 9496 2482 4597 9066 9712 7854 8984 4125 5015 3805 8114 5260 9254 753 3742 312 9989 9202 9840 9286 9936 4137 7078 9723 9960 5952 6452 1298 7630 4880 6248 7423 8586 7028 7326 2004 5424 8477 8714 1983 2598 9426 9732 7558 8054 381 4147 8085 9792 5732 9612 4925 6587 5042 9546 811 8324 9553 9968 5566 9135 4353 6556 8106 9057 8056 8897 684 6423 2112 5279 9899 9966 3902 5327 5269 9539 4515 9120 6593 8200 2122 2298 3227 5956 3411 8375 1908 6429 3015 5552 5759 9584 6074 7069 6199 6375 9987 9999 8539 9114 9425 9990 2553 9859 647 8002 5516 9844 8594 9551 3840 4460 1742 2799 8739 9806 1506 7339 855 8863 7856 9795 4815 9385 1779 8906 8168 9407 2370 7911 2319 4770 1505 3972 4317 7722 5424 6667 4280 6583 7880 8422 7527 9178 3083 9906 2097 9403 327 2866 8563 9027 9629 9718 8982 9099 4711 4734 2956 2962 9867 9892 999 6416 2029 2045 2038 4262 1892 9614 5310 9756 826 5083 5060 7227 1442 7414 4472 8457 5147 7878 3957 6045 95 1763 2286 8996 1304 6595 3654 9539 9494 9928 7952 9690 5100 7261 1175 4033 1598 1860 2899 4567 160 1648 7996 8492 5551 6741 357 2630 7207 9535 2887 8111 2275 2799 2057 8812 7812 9534 288 6786 3387 5682 1554 8605 6323 8812 6887 9752 5668 7174 2967 5826 4577 9130 4823 5308 6492 7848 7549 9794 6481 7120 9818 9960 8170 8388 8945 9587 912 7322 9806 9959 8800 9830 6262 6512 5584 8770 6804 6909 350 1769 889 6487 7050 8755 3727 9426 7695 8342 4396 9447 4448 6603 7231 9554 3817 4222 6912 8350 4328 4416 8860 9886 8111 9323 4306 8769 8728 9474 7166 7813 9779 9808 3671 3823 6512 6849 7049 7092 7711 8661 9781 9964 4096 7008 3445 4808 5912 9596 3232 5184 2205 9550 1028 9847 1587 8675 1228 2995 340 6013 2231 6191 448 7638 8856 9474 634 8018 6832 8623 211 6959 8676 9967 4373 7543 7565 7945 734 6792 180 9976 8509 9461 4041 6137 3532 8888 8654 9953 3734 6527 9323 9848 1189 6248 1764 8185 1361 5907 9271 9515 6758 8779 3823 9498 8507 9082 1768 1819 5221 8988 1656 8415 398 5642 8104 9076 7225 7354 8756 9433 9279 9424 6555 7553 8732 8843 3793 6725 3835 7839 266 3804 1265 2133 4046 7774 2919 8703 3470 9037 3121 7847 6561 8435 6534 6903 2037 2339 2755 8478 1473 2243 7761 8138 3423 4015 4927 6492 6888 8673 243 8907 5410 9865 9992 9998 8713 9212 1076 3977 9788 9973 4385 6231 7111 7505 7088 7291 9896 9903 9785 9876 2829 9334 4245 4831 3578 8001 6744 9478 6304 6338 8736 8939 1684 3058 4323 4369 7736 9883 6866 6896 6455 9760 229 4011 4375 8190 8195 8518 9899 9905 4187 4514 2162 7882 5301 6100 373 9135 3501 4755 614 3545 6203 7083 8539 8873 6303 7152 7108 9665 6773 8849 1670 5853 8074 9733 1651 9701 7493 9667 7190 8769 1410 4340 9351 9823 3464 8400 9626 9717 9637 9671 8925 8984 1035 3422 6813 8950 4783 8986 3366 6557 2154 7254 3332 6183 2151 7611 1094 1687 4129 4675 3839 5118 6478 9617 4820 5987 2773 6836 5777 5786 4714 9932 8124 8929 7589 8248 9809 9833 6508 6893 817 4965 9730 9736 728 2821 7349 8599 5398 9665 5983 6801 1616 8520 7854 8494 2304 2328 6005 6395 5730 9925 640 2190 6719 7943 7270 8355 4993 8590 6112 8434 2625 4847 1104 4715 2840 4575 5368 7137 7805 9189 6900 7642 9219 9428 3577 9712 1622 3387 7440 8102 3317 9445 2758 6690 991 4962 1905 3504 9524 9946 580 5119 2495 9502 4921 8538 5580 7627 4110 7940 7635 9319 5001 7121 3961 9931 6805 7690 365 3177 96 6111 3758 6862 7675 8954 2220 5535 3139 7869 4723 8421 6475 6597 1904 5770 1340 9902 4560 9817 2745 3772 1984 7754 9915 9949 3936 4024 5818 6368 9437 9753 2951 7337 284 9159 8206 8961 8855 9460 5811 9325 1605 8432 1023 1387 1183 6269 6476 9122 6773 7282 9415 9920 1257 1780 1691 9439 5854 8832 4018 8164 7514 9862 2034 3336 1969 6757 6742 8749 8804 9689 3495 7235 8114 8466 6570 7020 8434 9965 7956 8470 4460 7477 761 2845 1947 8875 197 8205 6125 7090 9923 9951 4897 7560 9338 9800 3128 9699 795 6359 6059 9436 4040 5246 6353 7313 7811 9801 2304 7685 2140 7942 1240 8370 5165 7338 5543 7226 8494 9238 5313 7843 4406 5748 9659 9712 2819 8811 2233 3609 225 3399 7923 9174 1262 7388 894 2457 4562 5639 7521 8395 4120 9905 4893 9361 2281 5200 2395 7507 1151 1771 6454 6654 6227 9321 4873 7322 7480 7699 1912 7589 5555 9728 5015 9705 7709 8164 463 9271 1761 8966 2129 4298 3271 8877 1211 5318 2419 5494 3391 9857 7012 7122 6738 6973 6497 8868 780 1697 1520 2502 36 8784 6890 9688 5723 6995 2981 7256 7944 8825 3921 8167 1940 3112 2155 2194 4599 6441 1015 7231 9960 9975 5343 5673 287 455 1450 2462 4307 6659 4640 6241 3087 8007 9450 9861 4522 9446 9866 9869 8694 9689 1762 9041 8853 9362 4843 9350 6389 9176 8620 9044 6850 8529 2459 8294 5375 7418 2435 3103 4011 5033 821 9521 21 1321 9122 9418 9197 9498 9890 9939 2223 9661 40 5929 2538 5740 9683 9760 388 6731 2597 8204 6575 8507 3409 5751 8290 9149 8697 9618 8987 9826 7236 8064 6717 9297 5826 7646 2537 3101 6085 8265 7739 7809 4173 6737 5975 9594 988 1533 1780 6136 6512 6856 3276 8255 1977 5276 8394 9760 3517 7649 1648 2152 5335 9792 444 6071 2919 3982 8952 9029 5760 8469 8611 9481 9158 9438 1005 5053 1801 9724 998 9693 738 4192 6096 8388 7912 9789 3060 8436 9148 9184 9399 9846 2532 8578 6479 9014 8874 9954 7857 9582 2185 3879 5132 5434 655 1878 4463 5764 9448 9490 4313 8597 3540 8588 4720 9165 5239 8795 1043 8525 1886 2507 1283 4322 7745 8285 3176 4328 6205 9360 4749 9460 1827 2491 66 775 1130 2451 3730 5824 4445 8105 6011 6569 8302 8793 457 2581 9489 9546 802 8448 8681 9069 1331 3495 1404 4825 2439 9811 6399 7541 5668 9824 3741 5156 334 3973 9253 9502 7813 7951 1585 3281 1764 8859 761 1605 6847 8842 9387 9701 7720 8291 8840 9412 2438 3053 2666 9530 6474 8233 4980 6686 7195 7564 4632 7426 4241 7315 7734 8621 7947 8510 1624 8336 4168 8417 1769 6865 3515 6560 7934 8374 1341 1376 1245 4086 5266 8465 6657 8014 8273 9280 8134 8137 1997 5082 1027 3418 8106 9150 9942 9974 1452 7391 2370 5725 8292 9986 76 3006 3398 6767 6865 7035 3673 6594 982 6914
样例输出
574 395 66 803 129 172 150 303 37 226 62 261 837 404 218 38 102 975 443 121 836 1355 151 213 156 202 1129 18 232 979 533 251 26 951 2 851 484 244 33 213 204 326 355 43 53 155 270 133 100 42 490 737 100 581 21 462 429 178 136 719 206 370 116 343 13 101 584 60 114 1 336 178 118 9 673 319 641 1245 1300 83 669 336 42 205 438 80 392 648 784 367 400 976 85 817 292 487 228 73 559 908 186 488 303 56 619 270 66 93 1303 422 1379 40 548 480 456 151 3 229 634 368 923 1036 540 184 521 20 373 3 628 795 115 124 261 562 58 177 467 198 239 192 839 610 570 875 8 1047 7 73 96 499 331 1055 949 361 156 723 1031 585 1 427 135 409 339 474 7 258 24 441 549 578 23 76 525 135 302 169 302 1009 52 17 792 107 124 362 478 501 3 849 265 521 367 597 1224 355 312 270 259 261 601 211 175 128 238 510 172 35 491 627 468 470 16 136 260 40 553 126 37 41 71 93 870 224 304 72 74 47 5 561 1092 271 346 734 707 2 738 8 245 964 317 818 894 58 12 202 6 824 309 213 56 52 1136 1032 208 894 71 99 250 2 295 476 295 338 91 1054 1044 366 102 723 595 11 464 403 117 163 1038 277 392 293 1187 107 181 473 904 1171 484 18 634 264 377 1430 604 107 507 615 65 398 704 582 951 709 300 338 48 311 578 823 1142 387 270 244 19 102 1330 418 69 63 39 1288 125 126 438 511 736 1266 33 184 645 16 343 510 909 259 198 597 1479 318 351 395 311 236 862 56 186 13 4 317 336 268 1037 993 116 1010 546 29 419 179 559 208 423 896 49 6 548 382 502 222 316 319 82 1121 1 39 679 139 467 144 3 67 659 27 84 240 381 41 371 1341 108 13 174 68 131 408 847 813 1026 0 107 0 887 26 254 363 32 500 49 42 1274 301 726 1167 363 138 255 174 152 328 10 97 4 86 730 73 71 328 103 164 138 638 588 497 1530 108 111 442 40 75 974 208 171 41 532 33 103 47 73 635 265 576 255 671 1167 68 522 327 140 128 911 493 9 213 640 678 234 30 413 738 703 381 569 152 31 0 86 92 1110 1148 650 154 94 184 170 905 1236 296 678 1090 187 840 381 404 502 184 342 78 242 1027 1109 452 71 17 16 4 2 4 851 3 358 1176 665 683 324 923 589 405 308 310 1012 824 879 70 264 322 465 43 255 278 72 178 403 349 783 92 1024 260 1048 345 1078 362 429 223 426 671 74 198 344 95 24 33 99 999 26 163 36 468 16 257 880 248 848 97 755 324 346 64 209 11 166 180 657 121 93 4 23 51 8 136 30 436 206 546 294 1118 1360 1082 300 924 612 1137 99 1158 257 1090 209 467 57 953 1555 151 314 799 210 413 89 793 985 717 47 296 849 87 8 557 1035 854 142 18 108 30 145 19 441 596 610 146 555 859 826 706 277 56 49 853 132 53 91 240 255 1370 673 0 75 473 31 277 52 28 1 16 971 83 656 407 6 34 235 7 330 4 494 648 563 44 1 49 870 120 1374 188 496 133 54 125 382 304 654 255 1234 331 230 477 77 734 17 6 7 393 314 625 477 784 427 831 94 82 195 463 175 614 2 789 119 99 4 58 666 2 358 180 640 122 1055 90 3 65 633 270 177 157 527 343 340 573 263 270 201 104 40 918 294 102 919 591 632 260 70 744 1059 535 300 570 251 317 897 127 492 989 464 191 518 705 550 17 600 1319 789 161 881 7 12 90 50 658 1392 111 95 521 1050 57 799 383 75 82 84 1191 439 614 363 214 737 291 140 563 52 68 238 75 444 355 1055 1275 146 7 397 78 985 883 505 179 139 303 816 883 1096 324 249 110 375 201 7 894 224 557 181 946 263 159 132 872 666 455 772 100 26 454 368 36 868 623 698 67 1372 1099 350 835 652 473 971 18 33 349 152 168 1398 417 190 640 129 629 196 5 277 969 4 52 34 175 346 241 730 68 735 0 158 1111 77 671 401 69 242 883 304 111 154 1347 263 52 55 7 1132 979 492 14 1021 844 279 351 121 142 135 116 378 268 97 322 11 386 537 86 682 52 741 515 211 616 86 670 908 163 10 401 140 53 645 1214 1338 566 338 288 800 7 73 908 370 173 258 273 43 209 193 6 627 747 657 526 1147 106 492 80 177 465 705 117 154 220 309 543 85 70 374 8 1185 61 352 547 1117 160 622 209 623 47 21 284 1083 140 291 52 86 88 104 1036 256 253 51 413 456 124 79 1031 628 793 457 65 4 460 473 200 145 0 485 395 149 5 917 518 263 530 504 25 437 927