P18667 [HackerEarth] "Promises are meant to be broken."
普及
题目描述

"Promises are meant to be broken."
Chotu being desperately in love with her crush made N promises to her on Promise Day. Each promise "i" is associated with an effort value Ei. The effort value of all the promises are distinct and each Effort value lies between 1 to N (both inclusive).
It was later he realised that he will not be able to fulfil all the N promises he made. After analysing all the N promises he came to a conclusion that he can only fulfil a promise "i" if and only if GCD(Ei, N) = D. Find out how many promises will Chotu be able to fulfil.

NOTE :
GCD(x, y) means the highest common factor that divides both x and y.

Input

First line of input contains the number T denoting number of test cases.

Each of the next T lines contain 2 space separated integers N and D
Output
Print T lines. Each containing a single integer denoting number Promises Chotu can make.

Constrains
1 ≤ T ≤ 1000
1 ≤ D ≤ N ≤ 10^6

SAMPLE INPUT
2
5 1
10 3

SAMPLE OUTPUT
4
0

Explanation

For the first sample case, GCD of (1, 5), (2, 5), (3, 5), (4, 5) is 1.

For the second sample case, no number has GCD = 3 with 10.

输入格式

见题面

输出格式

见题面

样例输入
1000 88971 15818 38286 26481 64215 23479 15129 6754 50701 46920 96072 7065 48223 12452 24916 8848 89650 69924 93559 32287 77003 54186 64669 51777 65695 51220 37840 14964 34221 959 25301 11020 59421 31002 21515 551 82786 25160 59431 51200 7613 3907 38957 32214 8870 6994 37757 34464 16676 16010 10698 4872 5715 763 26473 21443 75025 59085 93233 6745 91976 70417 38901 5776 50242 50195 20978 1437 35195 20592 79354 71965 50512 2519 50760 28007 99001 55039 67041 60659 34900 21922 82330 54056 68646 4615 20011 15377 55342 15444 54692 7897 63683 55752 5631 545 38467 17465 11166 3622 1418 1243 680 274 27873 26100 43181 22591 69244 14765 45727 18079 56203 10351 22981 13615 13136 11064 29521 1891 35418 13693 69841 53118 28393 12426 31530 26732 54990 48496 89093 24005 39127 825 95658 87000 49694 37567 9327 5387 14482 6527 87081 63804 3361 2796 13432 11820 1256 183 43875 3594 77061 3175 7615 5013 55617 54146 38948 10405 28971 9879 22802 8955 50738 17545 1229 460 38365 7770 20491 419 6694 1369 94734 60862 31276 7455 55175 38965 20805 11750 51515 5737 61627 50537 90967 74925 31661 17870 80067 13527 33065 26599 10826 10306 23279 18837 951 121 59631 31164 63843 21444 51083 10194 76661 32766 58496 57591 27776 634 80857 16999 16698 11378 67138 34636 36937 2616 92198 28059 6807 3113 6424 4410 76840 32814 84532 67134 9632 3632 54929 33539 13887 2090 67206 32205 62621 34080 94145 88089 87184 64623 12148 3635 97437 65777 82840 72797 20549 3398 95098 60572 8946 6916 6305 3605 88215 68889 61508 51299 73677 45894 65410 20803 565 528 98867 45148 58800 48252 71545 51906 76574 64550 52251 4809 68202 1747 32315 20542 31786 29127 30486 16280 20948 16691 26242 14922 7021 6840 37741 18345 69193 54833 14353 629 25767 4094 64406 57791 98321 54812 55087 12088 30748 14626 83971 67940 24381 21480 22731 5414 26712 2531 91820 77686 15614 3230 45377 28074 99463 15517 31877 13708 53915 47455 13078 11260 54197 25101 60487 46219 53607 25556 23238 4741 27481 29 70674 30436 87298 28134 12902 5086 55651 48302 54485 12859 70743 46543 20376 6851 26120 10157 28651 2384 67648 14414 86441 13639 89874 9751 87695 29733 26162 5101 61256 49627 67068 10858 74428 51212 13987 11586 27673 7147 86772 77636 8392 4106 57605 53582 76075 50755 2520 853 57398 9942 64251 3800 34645 13966 2503 2463 94606 34729 63430 30139 19546 6748 60318 31019 74004 17659 69700 5386 71259 31249 6263 1756 22846 3386 53650 39641 68069 42735 61548 16576 87132 32792 82470 6664 96398 31874 75142 28620 76461 4546 89656 37926 16506 5915 94904 1910 22154 3934 57034 50995 60169 25182 96541 16795 3084 242 54216 26852 49420 15582 59014 52912 60249 1531 23099 14300 34589 21925 91954 4125 64993 58298 20444 6589 13953 7901 13914 3296 74542 7902 51391 36383 40715 6078 13879 5612 80984 47033 85795 45082 95590 77466 19703 7421 31426 22351 50335 14472 65319 39734 69230 22632 48711 48408 53229 39126 28441 10135 74153 6724 27067 6135 3520 742 95675 16466 15361 14222 46653 18118 93406 15985 70766 1652 84479 21329 30073 14481 63727 22053 48949 32623 26695 8407 39733 22457 64857 45704 97822 74287 69871 37511 62927 3452 61333 37360 92060 23622 85094 30008 33872 28235 30014 7541 96143 78771 63549 31992 29449 20984 56152 25511 26764 364 6082 5356 9025 6243 68142 23357 20164 11056 51294 26728 98766 25177 94496 45285 41981 18181 86820 11524 32939 21185 99239 79569 67421 57652 71383 26092 53942 454 59837 22168 7831 4815 60780 35501 47915 3152 57845 17719 3535 970 22077 14307 7638 1583 77470 68854 37237 2932 82230 22203 48234 44539 21930 17154 13788 9846 27843 14 60203 30021 55599 10028 81493 76208 96563 12973 24275 15947 6969 3565 53469 24204 43383 21241 63794 55532 13364 7817 86960 2801 62414 34840 8840 7582 99319 70928 56873 29115 93920 43349 31443 26495 17323 11081 80142 7560 13436 9977 30227 15973 84861 68229 60306 42815 69856 2667 12752 685 79423 53 97746 6993 65278 29457 63532 30796 75091 63497 64659 15164 83744 22838 26272 6026 12968 12897 58550 7230 2524 112 96792 8374 80322 61971 55348 5164 63973 25204 55312 22953 47991 12856 69500 14020 46126 23771 42563 3568 14380 13971 26148 3740 118 28 33789 2578 46554 39156 60261 33435 2993 682 60915 60494 48782 6061 77711 61985 28265 24057 78703 66136 47974 18554 61037 43373 78366 10602 41809 19666 99518 36065 18667 188 34305 16956 17851 809 97943 72928 80255 77882 44868 39333 82296 19102 93217 18322 54774 17090 39868 18972 47437 30924 48161 46074 15184 13228 89426 44013 89375 12375 81817 78014 85944 60887 83954 40903 65727 6876 27102 207 82306 73548 15182 2696 84209 69638 31762 19076 64536 50058 20095 3361 81573 45325 20520 12466 70602 666 48986 39138 40985 5550 30085 12509 12551 9775 50421 26141 29058 22774 84268 1490 12519 4845 12966 8091 55211 31433 13816 4290 30586 30147 7154 3393 77420 22275 15467 6867 40644 20334 2205 826 2254 1563 55991 453 54698 49168 9884 2117 38700 30581 52422 32081 80621 37716 37593 11916 77509 4310 163 72 53187 49239 35303 28473 23675 6364 5987 2972 48332 21865 12689 10100 95794 57348 40664 14964 35548 19702 83533 4307 57659 9666 8976 4769 52764 38605 90389 31284 70328 3385 30607 6818 48306 9398 4267 3961 14615 9538 17597 8968 35244 18633 81788 2338 97344 82767 32589 20503 64031 45476 83618 55658 25455 12197 22978 19362 94280 91657 25367 4430 29313 25889 43431 10182 26593 9804 66320 24216 88513 83155 65948 4534 17762 7600 69030 39234 38281 224 10467 2432 12831 4961 69330 33511 89977 59169 71070 5263 2073 1162 46507 27062 83654 59180 47291 30736 88264 19276 29600 4590 44795 20196 30832 22701 80946 64998 24894 16397 81452 1216 82608 16314 13862 57 59690 38616 98275 40158 53120 13309 38415 6867 18753 18437 2384 1702 46073 32554 77843 19131 99180 19900 97567 96382 851 503 85524 5562 72763 22468 36047 16901 24937 22192 27676 10366 36161 3961 68294 58197 72609 66380 1800 222 99840 35413 7494 1120 67460 64460 76254 52923 98905 60095 75402 43371 76645 39591 27110 4101 78441 16000 19538 16425 43655 9808 27814 23733 9080 4691 63885 41291 83381 60925 21302 2100 38415 24348 29701 20029 31233 1041 95019 63794 8142 4235 96796 5637 87945 68228 59240 23271 53828 11052 63028 31094 83628 83542 86046 80563 72416 29311 35375 20570 11843 8136 67771 56142 23925 17807 53205 18135 87161 56132 83154 42230 99461 69045 26738 10393 75411 29933 46829 30092 16338 3164 77251 22224 82559 24233 34964 22543 81855 5357 45185 2730 4450 110 94830 15 58874 36161 43255 30148 12456 4103 52704 32037 6553 5293 49252 14840 36037 19058 65045 22079 24722 12464 28829 27953 94676 19754 73098 61293 54611 33331 60812 38445 65031 10953 15208 3153 86199 34072 41034 7798 63763 20137 49052 5283 54723 52038 68729 65043 90412 86773 28825 5874 67283 21723 6116 5000 58541 22639 22204 6286 63347 53174 60732 32146 92610 77756 83010 12699 78461 35242 23251 6432 4652 1318 20453 9128 93699 2828 96206 51665 98109 3527 91803 8053 67518 30840 11337 1602 12264 3400 76089 50517 9798 9151 5896 5218 51394 3505 7936 2692 79352 258 1215 301 71397 20881 28453 24171 30692 27405 74177 35646 98520 19067 20082 11235 75044 1208 70137 52436 77416 46009 35982 1975 9388 6193 20320 11154 6147 4610 58926 23716 40882 6919 35519 32880 37167 26155 54312 50986 83395 47676 88421 1755 21194 1486 39103 14485 97560 91740 66107 5999 32985 3905 10455 7911 8688 3518 98053 72949 22195 7546 91493 34709 76947 61253 15449 15023 83712 59779 12265 4763 57551 14394 78773 20758 14571 1069 72382 14593 98081 65785 27113 7413 99937 84203 1968 1161 11413 2265 64114 4898 77064 49677 17844 8643 71809 19522 74133 41108 44722 17367 72748 56776 5729 1251 70156 36145 30482 5871 76838 61363 44355 40572 29741 2735 38447 4182 47781 4468 97333 32314 33354 1639 36887 36221 12797 9629 71955 24159 482 297 10290 9589 84356 79439 97210 6906 63496 45946 15085 10379 76439 72814 21524 16695 97640 75058 58233 58215 92065 45669 15940 6197 19344 1686 65156 41993 9420 3416 88580 7644 91181 72723 66130 49130 64942 39029 55883 46385 16167 6607 9810 1185 5420 4151 67138 65138 98045 9857 10678 4916 95194 16705 41232 2223 57909 48778 40652 571 47863 45648 25491 11452 88457 87382 89735 25673 49843 26638 88442 36094 29935 3332 21589 5714 85368 76864 13854 879 43930 29684 75254 52013 35619 20499 12674 8790 67435 2098 45475 25810 11687 11167 58391 48482 54241 49159 63546 33329 83162 18194 92889 21443 2405 1170 94089 7305 16412 1653 62793 59507 32784 3824 39332 20527 59642 46776 24892 2519 49339 21538 25984 25670 15317 1442 77503 50432 93894 55197 22155 8089 97025 19545 88292 31596 48545 24276 15468 13819 66817 7778 37140 36843 35517 22159 35453 15044 70693 38519 43302 15559 12123 10868 63924 24325 94005 53279 96116 38033 95685 27189 14412 13243 83958 77750 93882 67307 57216 20679 63147 38880 10862 4981 46989 46344 44953 28611 72482 67657 92777 82374 36193 29046 95316 82161 17688 15553 84284 41097 50904 29645 92252 79282 90681 66832 29162 5525 72983 44589 47940 37701 72411 11516 69339 59548 21616 8702 39448 15271 65090 25207 67136 38320 65228 37705 60023 54513 54631 23662 67243 59895 50481 44411 41728 33659 72270 838 47570 40535 23102 2282 59944 9209 70493 1340 48827 41093 52307 24416 25686 6149 40929 32458 91607 24505 88857 74021 4819 885 94119 78732 65702 23334 53092 34608 69220 26041 32177 31115 24816 13005 58920 56444 31170 14373 31510 19325 59406 37611 51769 40042 96255 78839 94190 74441 26200 16304 28161 22775 10766 10134 53596 42455 81321 34541 46498 38000 66748 60646 48034 10085 66646 50529 57462 32549 22332 13909 39743 5824 93982 2270 86873 25378 66899 49493 50508 12871 52442 47163 9847 2139 32584 3266 66529 61859 82059 52537 99541 64406 2656 676 66266 22664 33163 24691 57827 40215 23796 9764 56571 44709 74097 47869 77556 49633 20405 145 11622 2334 26959 23570 10744 8012 23005 20498 26537 22401 12582 1121 4923 2910 39116 22493 28450 18999 45284 2790 72619 27847 52345 31438 42924 18119 3932 1138 68984 62769 73225 16459 19814 15447 91470 52711 49427 37567 61852 30278 76824 50848 20725 13221 72017 21625 40358 26114 69501 65129 50674 29026 96736 61110 310 57 86284 76937 2428 1361 45083 39381 47319 21742 62372 20832 12992 4316 30306 14251 69815 63128 38476 30974 33056 31502 95642 3341 84912 69352 41465 5277 87031 72377 9832 4522 14172 8558 33844 5093 17781 5570 97403 64928 42052 12407 28122 21202 1546 342 47924 13042 90425 235 80788 20082 61386 42324 70409 43922 67828 7583 47521 24621 35030 27578 97138 18857 73453 35283 29557 10258 77353 14411 45186 7074 11156 7358 73788 57487 31343 1909 67167 31434 1 1 47523 42697 71842 1198 90471 64348 20297 17717 54559 47977 15015 1771 75944 5434 25691 21405 57296 17452 59993 16578 23411 5196 59718 18038 37102 5534 80718 28719 78980 28445 81053 3379 60033 39615 75428 73346 38898 33968 85601 16434 51898 45965 78780 23452 81440 79850 55774 50448 2422 544 10692 6685 25477 5715 33114 5242 74791 176 81514 47642 89998 82723 92007 29021 76677 34374 58309 52103 48428 30793 60611 4896 54888 24851 77329 15852 15164 11189 48025 13050 62898 18020 92932 23347 84401 60469 61460 34472 15188 13100 93034 8073 10267 2964 43465 4053 94722 77502 48713 8959 33644 22302 94425 24489 19548 2150 32814 31017 8570 4770 72203 18258 9772 9540 95752 61476 32163 30312 60321 29684 78650 43671 90751 75938 5076 4113 1301 70 88454 65594 53759 15674 39454 19484 64847 50262 86481 43472 62964 6992 89725 78102 8087 1869 12126 6341 99099 57129 62622 4208 20904 2954 12231 833 1572 77 42884 26321 69001 24052 4238 1735 5096 2706 30898 14112 46489 39536 38906 27606 70238 31498 84625 45020 28462 809 24440 18113 71865 22227 54132 27007 95266 83360 61038 14 48544 28106 63612 41346 24925 1927 79621 74825 76476 19142 74067 28300 46831 20288 35563 21766
样例输出
0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 120 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 46 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 84 120 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 32 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0