P18705 [HackerEarth] Tanya has recently learned about Euler's totient function. So she started solving problems on it to clear her concepts.
普及
题目描述

Tanya has recently learned about Euler's totient function. So she started solving problems on it to clear her concepts.
But she got stuck on a problem and asks for your help. Tanya defines the problem as follows:

Given two integers "A" and "B", you have evaluate the value of F(A,B).

F(A,B) is defined as the summation of all phi(k) if k divides both "A" and "B". where phi(k) is Euler's totient function.

Help Tanya to compute the value of F(A,B).

Input:

First line contains an integer "t" , denoting the number of test cases.

Each test case has only line and contains two integer "A" and "B" , separated by a space.

Output:

Print the value of F(A,B) for each test case in a new line.

Constraints:

1 ≤ t ≤ 10^3

1 < A,B ≤ 10^5

SAMPLE INPUT
2
1 1
1 2

SAMPLE OUTPUT
1
1

输入格式

见题面

输出格式

见题面

样例输入
1000 94975 94975 21307 21307 32895 32895 3258 3258 26464 26464 14736 14736 41078 41078 1790 1790 71929 71929 11179 11179 62829 62829 95607 95607 12589 12589 93601 93601 56444 56444 16234 16234 91486 91486 20235 20235 39013 39013 2416 2416 44635 44635 13151 13151 25681 25681 18217 18217 87563 87563 75262 75262 16152 16152 22719 22719 88698 88698 66143 66143 61054 61054 24 24 3801 3801 93949 93949 19634 19634 30264 30264 25036 25036 60711 60711 32054 32054 13316 13316 88242 88242 94882 94882 8922 8922 830 830 4834 4834 81718 81718 33415 33415 12672 12672 18304 18304 72427 72427 31439 31439 62939 62939 1929 1929 57119 57119 81155 81155 89491 89491 32380 32380 13659 13659 28561 28561 37429 37429 96153 96153 89615 89615 37453 37453 99953 99953 99915 99915 57086 57086 46568 46568 24950 24950 34148 34148 94973 94973 38265 38265 22389 22389 6207 6207 63538 63538 39570 39570 27392 27392 45255 45255 72984 72984 40063 40063 63559 63559 45410 45410 71501 71501 26497 26497 63690 63690 28620 28620 24003 24003 53181 53181 77351 77351 37661 37661 81741 81741 14780 14780 50165 50165 87707 87707 68584 68584 50117 50117 87621 87621 25669 25669 13037 13037 28922 28922 76168 76168 8009 8009 83538 83538 14909 14909 30567 30567 47076 47076 54478 54478 57959 57959 92330 92330 27462 27462 98021 98021 55888 55888 89223 89223 85874 85874 98736 98736 52913 52913 30845 30845 22739 22739 22445 22445 24547 24547 76751 76751 20537 20537 39326 39326 26916 26916 24596 24596 24261 24261 93384 93384 28568 28568 49929 49929 22772 22772 57490 57490 42449 42449 47133 47133 57379 57379 57357 57357 77699 77699 4454 4454 11834 11834 35657 35657 96784 96784 55647 55647 50030 50030 69023 69023 61222 61222 52255 52255 67759 67759 30486 30486 99451 99451 6849 6849 69282 69282 23997 23997 83599 83599 6170 6170 63323 63323 26866 26866 30765 30765 87583 87583 36602 36602 59333 59333 53864 53864 59373 59373 33174 33174 12664 12664 6505 6505 90552 90552 70020 70020 556 556 95006 95006 98205 98205 52564 52564 8141 8141 70204 70204 18945 18945 77163 77163 47777 47777 71199 71199 61273 61273 78262 78262 70649 70649 68121 68121 63895 63895 94646 94646 68072 68072 70064 70064 74320 74320 11289 11289 829 829 78254 78254 47890 47890 60161 60161 48469 48469 7263 7263 9686 9686 61132 61132 30119 30119 237 237 31151 31151 30674 30674 11594 11594 29356 29356 83238 83238 19734 19734 15911 15911 2182 2182 13249 13249 63687 63687 89733 89733 74521 74521 41948 41948 60381 60381 58994 58994 5842 5842 71378 71378 43417 43417 92257 92257 45697 45697 54705 54705 93085 93085 40303 40303 2595 2595 69597 69597 88771 88771 26209 26209 79282 79282 49903 49903 56327 56327 95871 95871 97405 97405 87001 87001 7464 7464 43112 43112 86590 86590 43550 43550 59022 59022 5123 5123 56798 56798 22708 22708 94855 94855 47670 47670 81007 81007 71588 71588 23015 23015 3200 3200 42965 42965 66431 66431 95457 95457 5014 5014 21136 21136 4893 4893 45316 45316 40082 40082 74490 74490 50438 50438 66290 66290 70123 70123 340 340 22616 22616 82345 82345 14097 14097 25968 25968 89809 89809 57208 57208 12557 12557 49710 49710 16230 16230 34032 34032 22859 22859 55289 55289 28886 28886 86880 86880 52648 52648 473 473 9895 9895 55847 55847 59790 59790 92677 92677 67655 67655 64803 64803 13812 13812 72548 72548 26470 26470 53893 53893 63389 63389 76907 76907 20182 20182 49863 49863 93599 93599 59150 59150 32208 32208 24047 24047 1469 1469 38368 38368 81254 81254 14026 14026 4429 4429 13835 13835 48057 48057 27287 27287 85476 85476 93294 93294 14166 14166 38123 38123 93767 93767 24060 24060 10321 10321 53556 53556 33089 33089 77976 77976 34710 34710 46900 46900 66875 66875 61179 61179 17145 17145 46615 46615 54437 54437 53678 53678 12829 12829 64387 64387 29179 29179 61388 61388 88433 88433 30648 30648 16107 16107 69687 69687 61025 61025 20535 20535 99873 99873 25433 25433 47821 47821 85348 85348 18726 18726 61987 61987 23470 23470 28844 28844 2398 2398 33791 33791 98751 98751 35486 35486 28118 28118 33460 33460 98738 98738 11344 11344 10990 10990 32234 32234 74310 74310 65427 65427 2263 2263 87138 87138 46165 46165 31442 31442 48526 48526 34598 34598 78441 78441 80984 80984 20636 20636 39465 39465 1519 1519 36860 36860 64897 64897 49339 49339 22208 22208 99974 99974 27677 27677 62029 62029 28818 28818 46427 46427 12171 12171 27568 27568 98264 98264 40288 40288 77380 77380 13353 13353 67983 67983 88369 88369 61938 61938 42292 42292 70147 70147 64201 64201 45782 45782 16312 16312 11994 11994 10659 10659 67261 67261 90434 90434 91642 91642 4248 4248 29898 29898 93160 93160 41107 41107 11146 11146 58851 58851 63314 63314 11119 11119 2879 2879 41695 41695 56288 56288 65657 65657 53865 53865 208 208 63921 63921 94153 94153 77587 77587 93625 93625 78487 78487 65955 65955 55563 55563 20779 20779 52454 52454 19763 19763 66560 66560 68765 68765 31756 31756 93570 93570 52377 52377 38541 38541 85211 85211 56624 56624 68438 68438 94723 94723 97730 97730 79583 79583 53573 53573 77396 77396 7053 7053 72803 72803 19090 19090 63341 63341 38460 38460 72954 72954 63548 63548 18732 18732 83458 83458 41134 41134 12356 12356 61945 61945 23440 23440 67918 67918 99075 99075 75893 75893 4032 4032 81986 81986 61009 61009 52139 52139 75555 75555 13385 13385 90679 90679 60765 60765 86360 86360 75468 75468 55487 55487 84090 84090 71402 71402 25411 25411 77837 77837 78455 78455 98214 98214 13278 13278 41795 41795 36673 36673 2583 2583 21694 21694 71756 71756 86041 86041 62827 62827 84111 84111 64337 64337 2618 2618 68381 68381 79763 79763 78511 78511 88764 88764 61748 61748 55871 55871 57255 57255 53654 53654 85608 85608 64285 64285 30770 30770 71967 71967 39753 39753 86257 86257 72408 72408 11154 11154 28019 28019 50244 50244 5960 5960 26232 26232 79873 79873 47754 47754 79256 79256 82456 82456 85799 85799 67363 67363 84848 84848 48625 48625 51474 51474 49184 49184 67595 67595 36206 36206 45298 45298 62457 62457 41321 41321 7045 7045 18327 18327 98575 98575 77050 77050 3934 3934 62860 62860 7819 7819 75901 75901 18964 18964 10427 10427 48308 48308 46469 46469 38446 38446 14904 14904 52429 52429 81029 81029 94776 94776 16534 16534 76637 76637 77231 77231 2333 2333 43999 43999 62078 62078 67309 67309 11824 11824 27613 27613 51255 51255 64381 64381 72910 72910 13711 13711 5702 5702 96306 96306 32038 32038 20628 20628 89707 89707 52323 52323 99839 99839 97526 97526 44575 44575 18802 18802 7952 7952 9235 9235 81623 81623 62749 62749 24138 24138 34051 34051 43778 43778 35265 35265 66936 66936 36766 36766 28848 28848 85620 85620 97116 97116 7277 7277 69281 69281 8940 8940 34890 34890 20535 20535 89672 89672 24151 24151 34246 34246 95373 95373 36809 36809 82635 82635 16001 16001 26515 26515 51309 51309 15839 15839 24040 24040 95884 95884 50993 50993 48344 48344 5118 5118 32615 32615 11092 11092 45607 45607 83017 83017 71221 71221 97223 97223 66304 66304 24338 24338 26070 26070 68276 68276 21454 21454 33347 33347 37556 37556 46745 46745 68236 68236 74442 74442 36416 36416 8738 8738 8687 8687 31789 31789 45546 45546 7673 7673 64141 64141 88413 88413 58982 58982 96331 96331 12452 12452 54865 54865 63675 63675 77147 77147 76334 76334 12641 12641 88239 88239 38292 38292 12009 12009 75811 75811 35514 35514 94665 94665 149 149 61584 61584 62940 62940 21602 21602 11282 11282 16847 16847 68346 68346 95869 95869 91288 91288 21113 21113 4606 4606 99975 99975 69253 69253 66504 66504 23999 23999 33393 33393 54916 54916 82980 82980 46076 46076 83719 83719 54196 54196 26102 26102 60866 60866 46881 46881 38743 38743 65456 65456 85172 85172 67103 67103 41266 41266 37038 37038 61767 61767 57766 57766 14973 14973 41058 41058 95719 95719 26254 26254 57904 57904 80416 80416 22122 22122 49192 49192 1529 1529 26727 26727 49166 49166 70781 70781 9582 9582 89516 89516 20526 20526 64497 64497 72496 72496 66601 66601 48216 48216 43043 43043 9054 9054 25433 25433 89924 89924 64148 64148 90888 90888 91447 91447 31251 31251 48505 48505 28484 28484 9369 9369 22623 22623 43456 43456 50427 50427 18341 18341 69709 69709 8330 8330 98757 98757 8182 8182 57521 57521 285 285 34909 34909 23038 23038 71065 71065 44490 44490 12554 12554 91590 91590 25339 25339 1401 1401 74542 74542 73554 73554 44443 44443 99948 99948 15338 15338 50718 50718 64095 64095 6225 6225 58517 58517 11697 11697 71081 71081 87000 87000 21066 21066 93703 93703 46808 46808 87844 87844 12044 12044 32868 32868 96173 96173 10800 10800 41050 41050 70046 70046 27436 27436 92310 92310 9435 9435 98500 98500 53151 53151 21988 21988 6442 6442 78489 78489 39740 39740 97335 97335 68394 68394 535 535 97282 97282 83731 83731 51252 51252 61377 61377 6307 6307 9768 9768 89425 89425 77388 77388 13120 13120 10490 10490 71090 71090 76279 76279 98333 98333 99485 99485 9146 9146 10858 10858 26636 26636 66547 66547 80903 80903 54071 54071 58856 58856 90337 90337 68923 68923 12007 12007 28677 28677 91716 91716 90495 90495 68416 68416 89050 89050 58889 58889 85302 85302 86332 86332 42619 42619 36554 36554 64060 64060 65278 65278 62673 62673 53484 53484 42665 42665 92144 92144 80326 80326 30106 30106 68422 68422 95010 95010 45943 45943 93920 93920 5867 5867 72578 72578 60466 60466 3121 3121 43001 43001 19322 19322 93458 93458 11923 11923 47680 47680 38486 38486 3638 3638 38174 38174 23253 23253 9039 9039 13414 13414 8555 8555 11722 11722 72385 72385 45108 45108 92133 92133 37662 37662 24132 24132 45617 45617 80326 80326 32628 32628 42294 42294 26783 26783 1049 1049 37303 37303 72725 72725 11320 11320 43170 43170 45303 45303 71786 71786 46290 46290 4655 4655 7459 7459 56099 56099 16577 16577 55138 55138 94584 94584 36566 36566 93311 93311 17837 17837 61956 61956 23077 23077 26391 26391 73678 73678 95461 95461 87850 87850 65810 65810 33122 33122 28333 28333 27778 27778 29799 29799 60960 60960 70071 70071 72933 72933 78361 78361 7374 7374 45658 45658 89680 89680 66895 66895 7312 7312 61465 61465 29536 29536 11966 11966 68923 68923 85635 85635 44894 44894 40412 40412 96570 96570 97811 97811 50075 50075 14406 14406 59766 59766 73151 73151 57148 57148 49795 49795 68611 68611 44997 44997 15605 15605 18084 18084 89682 89682 43382 43382 64234 64234 50641 50641 29805 29805 37166 37166 29001 29001 53530 53530 82823 82823 18681 18681 20424 20424 6486 6486 96497 96497 49959 49959 34803 34803 81772 81772 51945 51945 96048 96048 22183 22183 48515 48515 93858 93858 72257 72257 62920 62920 69976 69976 61759 61759 36420 36420 19770 19770 30369 30369 81416 81416 35374 35374 48452 48452 87449 87449 95108 95108 29037 29037 38090 38090 24912 24912 66203 66203 83442 83442 78441 78441 65377 65377 18474 18474 15216 15216 71863 71863 31323 31323 81526 81526 23017 23017 13094 13094 33471 33471 19065 19065 51628 51628 81985 81985 29274 29274 40237 40237 61256 61256 99249 99249 1995 1995 97675 97675 19019 19019 48716 48716 95443 95443 70744 70744 13519 13519 82891 82891 82203 82203 42556 42556 37332 37332 7114 7114 8758 8758 20774 20774 1906 1906 74134 74134 55599 55599 33473 33473 62348 62348 86921 86921 14999 14999 1717 1717 14 14 48469 48469 20781 20781 67994 67994 46805 46805 66406 66406 8230 8230 8060 8060 65655 65655 26576 26576 22087 22087 1025 1025 75291 75291 33881 33881 88120 88120 88810 88810 33123 33123 70323 70323 31365 31365 70455 70455 93788 93788 56474 56474 7580 7580 95694 95694 46959 46959 63178 63178 29166 29166 9307 9307 50099 50099 44164 44164 11023 11023 66464 66464 8984 8984 48155 48155 34457 34457 55788 55788 14560 14560 59038 59038 80200 80200 96566 96566 1966 1966 18638 18638 97590 97590 77256 77256 52518 52518 2062 2062 82417 82417 1992 1992 72384 72384 30133 30133 72446 72446 66171 66171 86606 86606 96377 96377 78216 78216 33565 33565 75907 75907 7382 7382 59223 59223 42357 42357 67897 67897 86597 86597 8820 8820 93233 93233 51103 51103 59629 59629 49020 49020 65662 65662
样例输出
3 1 2 1 1 3 1 1 6 1 1 1 1 7 3 5 1 1 1 1 1 1 73 1 1 1 1 1 1 1 1 1 1 1 42 1 1 1 1 4 2 2 6 1 2 4 1 2 2 1 5 1 1 1 1 1 2 1 1 1 1 1 1 4 1 1 2 1 1 1 1 1 7 1 1 1 1 1 1 1 1 2 1 1 1 15 1 3 2 1 2 1 1 1 1 3 2 1 2 1 1 2 1 1 1 1 1 1 1 1 1 2 11 252 1 2 4 1 1 4 2 1 2 1 1 1 1 3 1 1 2 1 1 1 2 1 11 1 7 1 1 1 2 1 2 1 2 4 21 1 1 1 12 17 1 1 3 1 14 1 1 1 1 4 1 1 1 18 1 3 2 1 1 1 1 5 5 2 35 1 1 1 4 1 3 1 1 4 1 2 2 1 2 1 1 1 1 1 1 1 1 1 1 3 1 1 12 1 1 1 1 2 1 12 2 1 1 2 1 1 3 2 1 1 1 2 1 1 2 1 1 1 1 1 1 1 2 1 17 1 1 1 2 1 1 1 1 1 1 1 2 1 3 1 4 3 1 1 1 1 1 1 1 19 3 2 1 1 2 1 9 1 2 2 3 1 2 3 1 2 1 3 2 3 1 3 2 1 5 1 2 1 1 1 2 3 1 1 3 4 1 4 6 1 1 5 2 1 1 1 2 6 1 1 1 1 3 7 2 1 5 3 2 2 2 2 1 1 2 1 14 1 2 5 1 2 1 46 1 1 1 4 1 1 1 7 1 2 1 4 195 1 11 2 1 1 1 1 1 5 2 1 2 1 6 1 6 1 6 38 2 9 2 4 1 1 1 1 4 1 3 1 2 5 3 2 1 1 1 1 1 2 1 1 1 1 1 1 1 1 191 1 1 1 1 1 3 8 3 1 1 1 1 1 1 1 3 2 2 2 1 3 8 2 1 5 1 2 5 1 1 3 1 8 10 8 4 1 1 1 1 2 2 1 1 1 1 2 1 1 2 1 1 20 1 1 3 1 1 3 5 31 1 4 1 1 168 9 1 1 1 20 1 1 1 1 2 10 1 3 1 3 1 1 1 1 1 2 3 3 1 1 1 1 1 19 1 2 1 1 1 1 1 5 1 1 1 7 6 1 10 1 2 1 1 5 1 2 12 1 2 3 1 1 11 1 1 1 3 2 1 1 3 14 1 2 1 1 1 6 1 3 1 1 1 1 1 1 14 1 20 1 1 1 4 1 20 1 1 1 1 1 3 2 11 1 1 1 5 1 1 2 1 4 7 1 1 4 1 1 2 1 1 3 1 1 1 3 1 1 1 1 1 30 11 1 15 1 1 1 5 17 2 5 1 1 1 1 3 3 2 3 1 1 1 1 2 4 1 15 1 1 1 5 1 1 1 2 1 1 1 1 2 1 1 1 1 1 2 1 1 2 1 1 8 3 1 1 1 2 1 1 1 1 6 4 1 1 1 2 4 30 3 1 1 10 7 2 14 1 4 1 1 1 1 1 6 1 1 35 7 1 6 2 1 1 1 1 3 1 2 1 1 1 1 11 2 1 1 2 20 1 1 1 1 1 9 1 1 1 1 3 5 3 3 1 2 1 1 3 20 1 1 2 6 2 4 1 2 3 1 1 1 1 1 10 1 1 2 1 1 2 1 2 1 1 2 1 4 6 2 1 5 9 3 3 6 7 1 2 1 4 2 1 1 1 1 2 1 1 3 4 1 1 2 1 1 8 1 1 1 1 1 1 1 1 3 1 1 1 9 4 14 1 1 21 1 1 1 1 4 1 1 2 1 7 1 2 1 2 1 1 1 1 1 1 1 1 1 2 1 2 1 3 2 1 2 2 1 1 1 1 3 1 1 1 1 3 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 1 3 157 7 23 10 1 49 6 1 1 3 1 3 1 1 1 4 1 3 5 6 3 2 1 1 1 1 1 2 1 1 18 2 1 1 2 1 1 2 1 1 4 1 1 1 1 5 2 1 8 3 2 1 1 1 5 2 2 1 1 1 1 3 1 1 2 1 1 1 1 2 1 1 1 9 1 3 1 1 1 2 2 5 1 1 1 1 1 1 1 2 1 1 3 1 1 3 1 2 1 1 2 1 1 1 3 1 13 1 2 1 1 2 1 1 1 6 1 2 1 1 1 7 1 5 1 7 2 3 3 1 2 1 2 2 1 1 1 2 2 1 1 2 1 1 1