P20497 [HackerEarth] Chandu is working on Weird function these days. A weird function is defined as:
普及
题目描述

Chandu is working on Weird function these days. A weird function is defined as:
W(a,b) = MW(a) + MW(a+1) + MW(a+2)... + MW(b)
(a and b both inclusive)
where a and b are integers and MW is mini weird function, which is defined as:
MW(i) = p^i + q^i + ...
where p and q (less than or equal to i) are all possible integers such that gcd(p,i) = p, gcd(q,i)= q ... and so on.

For example:
MW(10) = 1^10 + 2^10 + 5^10 + 10^10
where gcd(1,10) = 1, gcd(2,10) = 2, gcd(5,10) = 5, gcd(10,10) = 10

Your task is to find W(a,b) for given a and b.

Input:
First line of input contains an integer t, which is the number of test cases. Each test case contains a single line containing two integers a and b.

Output:
Print W(a,b) for each test case modulo 10^9 + 7.

Constraints:
1 ≤ a,b ≤ 10^4
1 ≤ t ≤ 10^5

SAMPLE INPUT
2
2 2
2 3

SAMPLE OUTPUT
5
33

输入格式

见题面

输出格式

见题面

样例输入
10 4095 5432 3412 7428 3199 8651 614 3447 1850 7883 3599 7637 4210 7261 5755 7178 3360 3802 948 5121
样例输出
186445234 195666782 761509082 945308581 808678864 814781967 310757167 454632488 658623369 496817509 410902893 267291189 189661608 952646723 487087084 533022069 43632832 255777729 548542542 671317111 735552399 420325362 192822356 503701034 295318337 773931329 717311234 44468773 255673281 628086940 495861394 915158399 838617222 634656862 513404430 557603223 246218066 180787262 427510263 536706245 844708912 832459838 159035182 981848671 825778920 36743530 65675980 386839960 582721718 400271495 266015778 695907361 449853248 295986286 622779500 971507277 919221181 341458239 434644325 578300721 619402844 772926300 166023888 219262490 565510380 976520522 446780494 524467758 512925025 323035038 26041983 372967977 247596791 510203835 244391626 260391464 590146863 854956773 645786525 959919226 510278289 249708830 100154294 474840145 213585212 800561509 108400978 5373941 612595406 614026094 572327463 589907458 757463173 337749796 306012252 579476842 814159326 320897596 668917790 563220344 333324998 578431664 670822185 48046575 510177092 430359625 313312595 748642626 109143285 699126470 545086635 265777441 924262703 954729073 968979257 359866029 310179062 875691831 624085451 531666818 741007010 629990268 93208601 915123198 333150749 506281117 245795128 921698947 986402834 387801524 592897680 509881744 777414629 715951616 605038856 219917245 919322866 240292531 877404530 975274585 346609676 319993756 81801907 467952789 605966834 707909198 219678266 260573552 772030923 945201278 735619826 297392353 256075403 257940615 93707940 677628853 828925536 294454056 961353571 849994489 954539697 646269942 101612696 88837809 92545188 115146299 522609303 857656748 975083383 422351320 111765654 690681288 950702208 977038835 415488538 985511750 729295450 472125310 794496505 566759685 931570939 151064340 968088460 428867138 613509585 266085302 791044393 384468478 666243256 636718517 387887509 896063079 527727834 545540396 124349877 838936536 947717233 431146137 464665642 599368668 555751084 48534516 477411303 205345085 353464515 106790833 738861482 204227904 92772776 443987764 371493526 398064224 212277346 552127870 385017761 387509167 856523369 745774323 223695401 602684490 107788267 224232515 755583475 972425227 51871992 227940214 495455331 669777135 719009044 381825578 544612487 924495256 811356740 580078642 678288414 570835406 751478894 520649974 404888179 346417832 652217561 974569708 44162187 719000465 22939179 90493133 584754393 221049298 487112111 615634921 384465324 472861786 430743651 370084723 228493852 989394897 585337317 138243430 578922557 280387539 917899938 465547822 680215709 948796214 814217504 447326942 205740946 654272986 285574764 353085978 939672325 218419113 532762261 44139292 154156622 942349679 395626744 73891300 920769945 411827464 216994040 31382536 498174603 448496252 918868397 122711443 489558063 450959267 296655073 153311688 392264590 35295388 554530170 841987780 943528397 200032255 607840809 521407410 258871606 714205887 769415355 663103655 891850613 131890838 649225602 544644234 669979048 748542636 147709164 246543599 255838453 764025194 580612646 858539966 734736261 786738998 452147656 427270703 267166041 995626635 102023055 721680223 414346608 308337812 807979810 89645219 45726399 757965758 483081269 301242902 177642527 841540365 108398186 101589783 967308434 94231764 97557099 696464581 484536005 776533854 259219986 204556770 946350134 371448622 135627456 75006583 157573821 135690924 578416404 567028640 2827204 909505723 919863580 646814460 364374931 21399052 284845663 642901755 556753479 436406716 741337162 61482044 165934555 967255554 948214761 799978157 776316908 736135098 614874121 269746662 55430011 793341948 643550319 88304090 41120417 42096792 7964566 613118382 432642585 59306618 191090332 949389410 462272520 499012103 576735912 354405935 258711423 449656057 911797173 712743109 306444047 32571784 24763013 695911382 840492166 739094659 607930924 219404138 396187248 343390716 133218554 755949522 415560988 43631560 392983257 994682616 331935477 8472502 902139432 832166015 970845855 303178458 342630416 966442239 351358262 351558173 666574436 472525163 167301405 352026388 772393379 326538831 147212769 85540190 447268859 65961989 287314174 404127169 489528532 280717275 153572753 9816497 633957591 471167318 686217601 469984824 965715713 586451242 689207545 61443560 325028001 896185734 981115501 519056189 670507833 879282808 608046147 767535771 806586086 44275781 403061032 467598521 471471089 877118775 987367223 903110075 607379307 929970384 936394593 144398420 613172848 55128820 179460983 534067303 468172843 286350738 143809993 893728585 830841345 40520972 293393047 538693888 186802922 395451827 840164148 37318164 524706803 686653379 562256360 871988798 449993952 208289479 671708078 658009223 45279954 143603933 198255856 593731361 298193012 830290921 194059759 454847604 58044580 215290982 827253345 211692013 319101514 921170247 768366564 94151106 154970987 65749683 842184513 938946020 533963725 51219217 761735157 179170494 641732720 383942879 635923497 98800330 881501894 665567967 651527819 861145378 257184531 535932908 411877214 735717172 858024943 500682925 641313224 612922596 842240637 666813136 111793144 883610551 585645500 14824167 389267473 248448825 619902423 699648470 611306662 391920623 941060987 785137005 703905427 594612655 208006493 789708138 274573517 451310252 596901004 429684926 403210426 664979272 571997017 942446375 593502973 62080601 641049344 470319037 316049634 526615312 430999813 2306867 322869350 837277361 213647612 314382714 987504485 420781670 826030582 476103280 721709241 894462419 715152561 561299388 646208115 896483453 196295439 518819610 665198748 978121965 962309562 120516423 815109194 904925820 163664893 11400210 758042431 496653104 607442850 587674053 50081384 773970699 699706481 39929209 947548154 753420438 457198700 455667724 5292516 6056246 636810551 692953954 413554706 532125801 499560090 439702329 171768015 840056660 368763062 724181666 80100522 405467466 114585844 845917092 923774595 141300228 625042774 498114947 725588887 695355905 681842469 57799960 386329806 828073666 938014393 274292322 307145683 204859803 881152733 637887175 885952824 789366885 718021941 444952391 383302636 328999427 350424775 254657254 437893125 322812022 121895485 244918608 194357430 277800604 444815880 349525274 509835150 534523892 991336938 954821782 807305937 209084968 827786028 419126746 764074854 910230948 357335152 244367400 414809421 417941547 254413874 116389138 794861461 786593505 120192972 834465997 393751717 877981383 592671550 503074423 849617710 442430468 705938640 574619350 738451837 446419103 221771288 38186518 477231363 346030706 458878962 835557185 908117874 896194197 618854219 496447857 464551114 98492377 241091389 843778150 548137820 731033485 509210776 731030397 448591605 902534924 65265684 204349661 25433932 152525618 211044639 622158439 242319542 95637652 955040396 378923369 988825779 594744953 325322059 276890438 858761711 420650780 747572681 690022678 208142338 602476417 175915404 123262498 902150464 301359689 887741109 697217696 335442243 552437806 491987044 397617580 45241076 852575169 310144655 854551679 835563191 981397012 442571247 59425712 570927540 584318854 312372418 916271971 342420311 498873714 251035029 515513851 987967343 567140739 672853088 687687695 333769374 968841851 155106471 904328395 841645042 697086129 710737783 551126420 78267441 776334312 864411819 407323487 815895536 958283092 79921791 107734049 997927195 952568675 553030006 721439565 444839435 509302054 178388239 460896144 143683005 297808597 279490057 737048051 274327445 547239959 796143574 767766367 649789532 608421518 963046764 216034454 199439481 212810946 880747690 656666214 701114093 541563390 333061224 13322740 813089395 802716684 621570303 629053010 372251544 667967693 992969379 307804321 107152050 137083303 395896357 798443671 838839117 331644675 671362148 179986594 427853187 357582294 58237821 668237313 660589704 792929079 84923776 997586736 236725148 962168489 312091140 942615520 432943458 712201785 478201825 374817726 442980030 9641999 231445537 517258767 51638369 16700676 926253102 876845571 471233707 717650389 865713747 290339502 557678347 512995149 510741329 302828562 967075891 177121842 760037990 949043069 255840943 318385088 235313724 524335016 358481721 540232058 417668632 863426385 700737011 622033332 826009891 980435022 14983999 779379055 869341319 524212457 256230507 709067727 596380935 422511788 433724289 254839717 313999845 535842865 626984564 613329263 705259160 370832555 686003617 553886062 665304096 904728640 360597061 862712940 590078327 857890555 255391906 510497008 644659908 780729071 935745041 326817612 440225541 159737828 243000824 607539473 48207269 415433154 424558523 781772272 204820542 579410236 903000209 772629557 895105690 971039839 727000505 804652701 575852753 250288372 940432634 887401415 193141004 4654410 506928130 407130081 390158836 820277326 542136569 879762658 947377704 855722666 511423665 257028546 624476439 797622286 122683982 949397566 716487638 818639441 940087512 230025479 709584025 612511729 6411269 185137208 878730820 616526539 355660417 493062892 378939243 633878520 593489908 841831602 838123262 123682938 388161908 54619769 429238751 240673344 794163752 802436248 561895211 794091666 136082224 280792896 164157069 843197987 771602644 807605423 868376153 403245400 237333973 263771059 179351334 362787767 957140260 819813816 805724629 882109339 483168776 761920321 352550313 373835942 630356282 958566609 413774551 478730101 948220586 973077700 422407811 609092357 582627399 669854650 979445834 486316074 916570177 814040471 360376286 874834253 412319225 525634277 631621396 159307351 12335893 616490850 135841527 21726879 462943663 553848986 285655134 20841147 849969549 799102136 143932185 130863418 179446658 73229711 702805654 772565718 318159180 964201621