P14042 [HackerEarth] Ma5termind is having his birthday this weekend. Yeah !! You all are invited . Ma5termind wants to send an invitation to those groups of people which he finds interesting. A group of N pe
普及-
题目描述

Ma5termind is having his birthday this weekend. Yeah !! You all are invited . Ma5termind wants to send an invitation to those groups of people which he finds interesting. A group of N people is said to be interesting only if the number of their possible circular permutations is divisible by N. Now, Ma5termind got confused as he is having all the groups having number of people belongs to [L,R] (both inclusive). Help him in find the minimum number of invitation cards required and win yourself a chance to attend Ma5termind's birthday party .

[INPUT:]

First line of the input contains a single integer T denoting the number of test cases. First and the only line of each test case consists of two space separated integers L and R denoting the range such that N belongs to [L,R] (both inclusive).

[OUTPUT:]

Output consists of T lines each containing the answer to the corresponding test case denoting the minimum number of invitation cards required by the Ma5termind.

[CONSTRAINTS:]

T ≤ 10^6

1 ≤ L ≤ R ≤ 10^6

SAMPLE INPUT
1
10 15SAMPLE OUTPUT
4

Explanation

For all 'n' belongs to the set {10,12,14,15} people . Group is interesting so, ma5termind will require 4 invitation cards in all.

输入格式

见题面

输出格式

见题面

样例输入
101 1 10 757163 757263 280037 280137 624993 625093 761529 761629 370994 371094 480351 480451 109921 110021 560866 560966 381426 381526 447779 447879 849950 850050 691267 691367 509772 509872 729811 729911 601010 601110 713298 713398 744164 744264 822340 822440 518439 518539 121585 121685 38545 38645 636460 636560 184775 184875 599339 599439 197944 198044 863789 863889 785331 785431 928406 928506 701648 701748 488790 488890 805706 805806 86165 86265 592485 592585 413500 413600 319135 319235 200834 200934 574401 574501 272170 272270 291697 291797 615916 616016 159008 159108 710605 710705 613323 613423 554903 555003 812392 812492 264100 264200 53895 53995 177815 177915 429542 429642 895689 895789 390139 390239 693769 693869 41274 41374 529188 529288 50649 50749 869480 869580 286918 287018 163826 163926 2094 2194 87698 87798 543103 543203 623108 623208 193668 193768 72149 72249 266465 266565 902271 902371 138727 138827 207410 207510 519779 519879 55361 55461 607554 607654 383179 383279 198389 198489 442939 443039 3044 3144 227318 227418 746812 746912 42552 42652 226249 226349 31076 31176 644375 644475 715186 715286 419316 419416 989253 989353 705664 705764 350698 350798 892748 892848 719839 719939 92736 92836 419360 419460 154236 154336 997264 997364 158251 158351 235011 235111 744529 744629 7193 7293 259844 259944 97824 97924 344046 344146 573399 573499
样例输出
927 926 924 936 923 926 926 920 918 925 924 925 924 935 933 920 931 923 934 915 912 922 916 916 927 928 926 929 933 920 926 918 932 918 913 925 925 915 930 928 915 923 922 926 927 916 916 908 931 928 926 934 916 925 920 928 921 913 912 918 918 929 919 920 915 931 920 908 925 918 921 916 921 915 915 928 935 913 928 907 922 934 926 905 931 921 930 926 921 932 911 904 917 930 934 906 920 916 934 933 920 934 920 905 927 925 923 918 919 919 924 932 911 928 919 919 933 907 908 923 931 926 925 921 923 932 921 910 920 914 925 930 934 921 922 929 921 899 921 917 930 917 923 933 925 916 915 928 931 930 909 908 900 922 931 930 932 936 929 926 932 919 909 936 914 932 912 933 926 921 926 924 928 932 926 935 927 939 916 923 924 926 913 933 920 924 931 922 923 918 914 919 930 917 935 910 923 926 919 930 914 911 936 920 926 921 924 933 921 912 915 924 927 921 931 914 932 917 930 913 938 926 915 920 908 923 920 927 925 920 915 922 911 928 898 921 936 924 929 926 912 929 914 922 929 921 921 923 939 908 932 924 932 928 918 918 920 937 931 912 921 919 916 922 932 927 920 933 914 904 930 922 924 920 916 924 918 919 939 928 929 937 924 916 921 922 932 923 918 928 927 925 913 932 930 908 926 904 931 931 934 924 911 924 931 911 921 908 913 915 930 927 919 923 929 915 925 929 930 917 923 923 920 907 922 928 922 907 934 916 900 920 930 924 926 939 925 928 926 920 922 922 932 916 916 928 922 919 923 917 906 918 926 929 930 920 918 920 921 926 928 915 936 909 900 929 928 921 928 921 916 918 921 926 928 934 921 919 929 928 921 917 915 916 918 919 923 920 925 925 929 925 932 916 934 929 920 933 924 931 929 917 931 925 932 917 922 925 927 927 913 930 911 927 920 922 931 920 936 938 915 922 930 918 917 926 932 910 930 934 933 923 927 920 925 933 920 922 920 926 925 939 916 933 931 928 917 920 924 917 912 920 916 916 925 931 928 919 926 932 916 915 923 926 915 924 927 925 924 913 934 922 926 917 911 931 914 899 905 918 917 926 925 909 909 912 917 924 927 925 916 918 919 919 938 920 928 930 915 921 932 908 912 923 930 916 928 919 928 933 923 927 933 919 922 898 922 931 928 927 912 919 925 902 930 931 911 932 917 925 933 925 942 929 928 901 928 934 933 931 923 931 928 926 916 930 920 921 919 936 927 924 935 918 921 924 901 929 922 925 929 928 920 922 922 886 913 922 940 906 931 920 929 925 932 914 914 918 928 929 922 926 922 930 937 920 925 921 927 923 934 926 934 921 929 924 914 921 917 916 922 927 925 933 907 925 928 919 934 903 929 916 933 933 929 918 931 918 930 897 924 928 924 924 904 936 916 914 917 912 920 923 928 915 930 935 925 916 923 932 928 924 922 928 919 933 925 926 949 920 938 891 917 923 929 923 866 929 896 919 943 913 926 911 923 929 930 919 916 935 930 905 927 938 920 932 923 921 925 926 916 913 910 936 921 933 914 924 931 915 929 923 924 933 915 929 925 925 916 923 903 922 920 932 932 932 923 923 924 909 910 914 915 917 929 929 926 920 931 919 927 910 927 913 928 920 911 922 914 934 929 921 916 920 923 919 923 913 930 925 917 916 918 934 929 923 934 922 919 922 922 929 913 920 939 933 915 905 917 913 933 919 929 919 920 919 928 922 928 905 914 923 923 920 926 934 905 916 929 918 916 931 913 918 922 916 924 915 935 929 922 929 925 908 926 922 921 918 924 903 928 926 922 908 928 924 928 906 936 924 916 915 925 923 930 924 912 930 916 925 941 919 923 921 919 917 916 927 929 941 916 911 932 890 919 924 925 916 920 905 937 920 935 932 915 918 923 922 928 923 917 923 929 919 925 922 938 915 929 911 916 920 924 933 921 925 918 908 926 928 927 928 920 919 916 931 914 930 919 928 925 935 928 930 933 920 927 941 918 935 936 931 923 932 931 920 919 926 917 920 898 928 923 930 919 925 923 928 936 928 926 931 929 934 925 922 917 917 939 932 928 927 923 923 918 922 915 918 926 933 913 914 919 928 914 928 932 927 926 890 924 932 927 924 927 923 931 924 917 934 917 926 926 930 923 926 926 913 918 923 932 919 924 924 926 923 908 925 914 916 937 910 918 918 928 934 921 923 912 909 904 925 910 934 926 921 930 901 931 937 925 927 922 918 927 928 935 927 923 935