Problem: Two soldiers are playing a game. At the beginning first of them chooses a positive integer n and gives it to the second soldier. Then the second one tries to make maximum possible number of rounds. Each round consists of choosing a positive integer x > 1, such that n is divisible by x and replacing n with n / x. When n becomes equal to 1 and there is no more possible valid moves the game is over and the score of the second soldier is equal to the number of rounds he performed.

To make the game more interesting, first soldier chooses n of form a! / b! for some positive integer a and b (a ≥ b). Here by k! we denote the factorial of k that is defined as a product of all positive integers not large than k.

What is the maximum possible score of the second soldier?

Input

First line of input consists of single integer t (1 ≤ t ≤ 1 000 000) denoting number of games soldiers play.

Then follow t lines, each contains pair of integers a and b (1 ≤ b ≤ a ≤ 5 000 000) defining the value of n for a game.

Output

For each game output a maximum score that the second soldier can get.

Examples

Input

2
3 1
6 3


Output

2
5

Solution (in JAVA):

Solution:
/*
                                                                    ..::..                                                                            
                                                               .:ii77v7v7v7r::.                                                                       
                                                     .....:rJj211sJLLvLvLvsYuuIU2s7:                                                                  
                                               .:r7ju1juJuuusYvLvL7v7v7v7v7L7LvsLJu2uYi.                                                              
                                            :rsj1JjYsLYLYLYvv7v7v777v7v777v777v7v7vvYY11ui.                                                           
                                         :7uuuYYvvvv7v7v7v7v777v7v7v7v7v7v7rrvr7777v7vvYL11L.                                                         
                                      :7ujJvLvv7v7v7v777v7v777v7v7v7v7v7v771QSririr7v7v7v7YsUI7.                                                      
                                   .iJjjLL7v7v7v777v7v7v7v7v7v7v777v7v777v75dgP5jjJ77v7v7v7LvsJ2Jr                                                    
                                 .7sJYLvv7v7v7v7v7v7v7v7v7v7v7v7v7v7v7v7v77rri7IDQRr77v777v7v7vvsu2r                                                  
                               .YKLJuv7v7v7v7v7v777v7777777v7v7v7v7vrv7v7v7vrrXZEEbLi7777v7v7v7v7vv52.                                                
                             .uS1LUjL777v7v7v7v777v7v7v7v7v7v7v7v777s77777v77rPgEKZdYr77v7v7v7v7v7vYXPr                                               
   ..                      .vIL7sU7vv77v7v7v7v7v7v777v77777v7v7v7v77L577L7r777rJSEbDbX77777777777v777sXv                                              
    :7r                 .:vJLrLUJiY17777v77777v77777v7v777777777v777r75rvULr7r7ir7JUZgP77777v777v777v7vs17.                                           
      i2j7:.     ......JUjYvrJu7iv27r7rv777777777v777777rrr77v7v77777r7Krruurrr7rriUEsr7r77v777v7v777v7vL1u7                                          
        iJqqq5S2525Jr::sUJsr2Jrv7I7r7rUL777r7r77v7777rri7jjr777777v7vrrYb7rYX7rrLv7QYi77777r777777v7v777v7JY1r                                        
          .:7j1525IKSIj77Jiqu7UYsur7rUJ77777rus7777rirYXEg7r7v777v7777rrYuvi7D2Xd US:777777U777v77777Y7vLYYSs2J:                                      
                ...     . :irX27KvvrIj77v77r2u77vrr72bgdgY7Uv7v7777r77777Y7Jr7BQ iB7L7v7777ruLr7v7vvJIKur  YsrUX7                                     
                      .Y:.: i:.rJrr25vYJYYLPULYjvubBBBRQbj5JYsLLv7rj7vvv71iiJrYi riUXJv7777jrLLrvYv7r:.:.:r77r.7P1                                    
                     :jLs2.i.  :: .r..:.::Ji::i:ivJ77rir7...... ivrbJr. iY1 rjrj. rr.  .YY7jZXP7       .72IjvLv .Kq.                                  
                    i5K7JUSL:. r  i.     r             .   . ..:777UY7. :L1  jvu7    .UXY7vLJDEg: .::rvjv77YuUj5  2P                                  
                   :U:jr12svUUsIiv7.:...v.......::iirYqSvrvvYYJLvrjrs7vrv7U. .57I. . .i:iL7r72gZQs7YJLYvv77r77J1g. v5                                 
                   X :JrPsrLYrLKLq7sYsvPJvvv7dRRMQgQBQRgrvvL7v77r7u:jv77771.  rJui ...  .jvrri7Pggr77v7v777777r7YIi:Ev                                
                  rj LvsIrvY   7UL77vr5s777r5DPqqSbEPPdrvr77777rrsv.7v7r7r1.  .ujr ....7svYr7riiuRPi77777777v777v7ss15r                               
                  2i js5rvvu   iI777ruur77iYEqXK5bPXKErJ7777r7r7rI:.:YirirY    7J7 ... .:rrrr7rri7Mur77v7v777v777v7v7vJ2J7:.                          
                  2: iZv7vuL.  71r7rvI777rrqbSX5dqSXZ7Y7rr77777rU7: .7iir72.::.rqr  ... :iurir7r7i7X77777777v7v7v7v777vvsjU1uvr:.             .       
                  rr  P77J     YL77rULr7rrsESSSZKXXEsYrr77r777rsv.  7EdgEMPYYYrvQs....  iDMqvrirr7iYJr77727rr7777v7v7v7v7vvYLjJU1uLvri:::::i7I.       
                   v ru7vL     vv77v2r7r77XqXSESSXEjvrrr7r7r7rYv..jQBd17rs      P  .... .IBbZXYiir7rI77777K2Lrrirr77v7v777v7v7v7LYu1IIKXPPEKJ.        
                    :U77uKr:   rvvr277rivvPKXE5SSdULrrr7r7r7rY7:KBg:rr:isi   . iu  ..... .1DqPPXsrirJjr777rgRZK5Jvrrirr7777v7vvsvvvsLJYvr:.           
                    .vYvUuYU   iL7vUrrLKgqdPgqqqPu7i7rrr7r7rJr7Bd.  7rrLv   ..... .......  LQPSKZbj:r1r777riPDddEddK2Y7irrrr7rsIJi.                   
                    iLvU.svsJisj77sJJbdRjXdgKPPQQSiirr7jrrvurJd.   vSL1I..:.       ....... .DBbqIqES:J77777riqZPXqqdbEbPUJ7rirr77Lv7:.                
                    7YJ7 Lv7BZ5u7rUvsrv7.1g5SPgjLqg1rvurvsYi:i   :r5LL7                 ...  2QdP5XbX7Lr7777riqEPXKXqKPbDZDP5Y7r77vY1UUr.             
                   .Ljj: 77YBi 277Uvr71iYRKXDgJrii7ZDu7Jvr::.   :r:1Li    IY72SPqdXJ.    . .  7gXX5SPKvrr777rriKEqXqXPZQQBBBBBBRPIJJsjJI2Y.           
                   :LYI  i7jBJ 1vr577vYrMPqd1:i7UI1rJ57ii::  .. . vI. 7MBBBBBBBBBBBBBBdi    . .5dKX5Kbgr777777riKEqXqP2ri:i:ii77YLsYJJ2u22Ki          
                   rLsJ  :rqr  177U7r1rqDKJi:rirrvvr:::i.. ..... r5 .RQBB: XgqqEi.dg:QBBBP.  .  dgXXbQB1Lu7777rriKZdqDL                :71UPi         
                   7jYs  .7IP. rLrI77LYQDQBBBBQU:  .::.   ..... .i  ::BE  rBdPEQ. IB1 SBBMS..  .BPqRq:   :1v7777riPPQQQDi                 ijP.        
                   7LYY   ruQBJ.LrjLrLIQQBBb72BBBBv    . .......    .dr   rBgZMBBBKig: BB  . . :iQQr  .:.  1v7r7rr7i 7QBBb                  Lr        
                   :LI5   ivMDEES:vY7KBBBY   RgPgMBR  ........... . :      BZrKBBBg:Zs Qr   ...  Q.  :s77v .I77vvr7s:  7BBB:                 :        
                   :sU1:  .vDXgDZriJ1BQBP . XBPdB  BZ  ... . ... ... ..    v.  2QB:.B: r   ...  ..  v. ii.  7Yr7U1rruv   dBB:                         
                    j. L   :g.rBg5ir5S7gB   QBggBM2KB  ........ . . ....           .j   ........   iL:iii   rvrrrKqrrs5.  vBB                         
                    r7 :r   UM 7BQsi2Y .Bs  XBD5BBBiB. ....... . ........    jK7ivv:  ............  7:::s:  ubirrrbgYr7Sv  .BI                        
                    .s  :i  :Bs rQ1rrU:.:L. :P  .Q:7B   ..... . . . .......   PM2:  ... ..... ...  .v::is   RgKrii7EMXLrs2i .K                        
                     r:  ..  7B: iB7rsr:i:.        BY  . ... ... ............    .....  .... ...  .virrL.  qDPbP7iivdDES7rL1.                         
                      i       vB. QQr7U:: ..  QEIKBr  . . . ... ... . ......... ......... ....... s77:.   qgqXKPdLi:sZPbE5YrYvi                       
                               iM :BRr1v  .. .7Ku:   . . . . ... ..... . . . ................... .si    .ggqXX5KKZjiiqbPqEdPjvvs7i.                   
                                 7vjRZir  ...       . ..: . . . . ... . . . .....::.... .........      7QdKSXSXSKKD1irDPbPEEgZP2usjv7i:....i7:        
                                  :YKDXr  ...... ... . r:  . . . . ... ... . .................       :PQPK5XSXSXSKqDU:1QQQRQRQQQMgMQRQMQQRdu.         
                                   :SPdg7 ..:........  .. ... . . ... . . ... . . . .........  :..iYZMEXKSXSKXXSKSqqDs7Ii:::rv5PBg7i7rr:.             
                                   :2bSEg .......... .   . . ... ... . . ... . . . ... . ...  uBgMMgPKSXSX5XSXSKSqSqqDJ:        .U5                   
                                  .iSPKSQ7  ..... . . . ... . . . . . . . . . ... . . .....  7QKKSKSXSKSXSXSKSKSKSqSqbP7          :Dr                 
                                  .7XbSKqM   . ..... ... . . . . . . . ... . . . ... ... .  7QKS5S5XSKSK5KSXSKXPKqSqXPEJ           .D.                
                                  :rEKX5Kgu  ........ ..... . . . . . . ... ... ..... . .  YQKXIX5XIXSKSKSKXqKgZdPPXqKZE.           r:                
                                  :udK5XSPQ. ..... . . . .       . . ... . ... .......    XQXX5S5XSKSXSKXKXqKZ77dZbPKPqgS                             
                                  7bbXKSKSDP  ............ :i.:.. . . . ... . ... ...   iDgXSIXIXSPgPSKXqSKXqEi .2MDEPPbR1                            
                                 .IBgXSqKgbQK    ......... . ..::. . . . ... . . . .   uQP5XIXIXXqKuPqXKSKXKXZP   :SDQgggBS.                          
                                 YB2qqKKdrbPQE.   ....... . .   ... . ... . .....   .ii5Z5S5S5SSKP7 5KPXKXKSqPR.    .7SbRBBQXr.                       
                                rBJ 1dKE1 .PEMQU.    ..... ......... . ... . . .  .iri.KPSISIX5Kqg: JPqqXqSqXPD2         :i77rii:.                    
                               iBu  YPdZ7  :PEdMQI:      ........ . . . . . .   .i7i:..PPSSIX5XSPM. 2bbXqXKSqXdM:                                     
                              7Qr   iddMr   :PdDqBQZji       . . ........    ..rri:::::RgPXX5XSqPg  vZPPqqKbSqPgE                                     
                            .vL     .qgMr    :EQr.QRRQg5v.      ..... .    .irr:::::::i7vEgPK5KSdP  :qZZMPPEgXEZQX                                    
                           .:.       IgQ7     .dB. qQZPDgQD5r:....      .irri:::::::::i:  7MPKXPPP   XRJ:RDEdSr2RBE.                                  
                                     :DQj       1Bv igQEDDQBBB2.:::.::irri::::::::::::i7   .gPPRgE   7QS  YEQMP: .JXi                                 
                                      7RZ        :d7 .IMq5Uj5I     .Yv:::::::::::::::::7r:. vRdJdB.   Pg   .7bQBI.                                    
                                       uB.          .       :      ..ri:::::::::::::::i:Yj. :Qg  P1   rQ:     :JgBQ7.                                 
                                        X2      .:.. :.  . r      .. iL::::::::::i:iir77: .. gR   r.   XL         .7Lr.                               
                                         v.    .:.. ri....::      :.:Ys.::i:i:i::ir77i.  .:. 1B:        j                                             
                                          :... 7.. ir.....r      ..:vr7::i:i:ii777:.   .::.. iuv.        .                                            
                                          ..  :i. :7......7      :.visi:i:ii7v7:.     ::......srsv.                                                   
                                         i.   7...7......:i     ..ivrr:iivvr:       .:::.... .YrrvJ.                                                  
                                      .. i   :i..r:.....ri      ..Liiivvr.        .::...... :J7irr7J.                                                 
                                    .    i   7..:7 ....7.      .i:Yrv7:          .::...:.. rjrrrrrr7v:.                                               
                                  ...:i  i  :i. 7.....r      :7i:r1.            .::.:.:...vjrrrrrrrr7YU7:.                                            
*/

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.Map.*;

public class Main
{
	static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

	static int zhong[] =
	{ -1, 1, 0, 0, -1, -1, 1, 1 };
	static int hen[] =
	{ 0, 0, -1, 1, -1, 1, -1, 1 };

	static int N = 50;

	public static void main(String[] args) throws IOException
	{
		int N = (int) 5e6;

		long shu[] = new long[N + 10];

		for (int i = 2; i <= N; i++)
		{
			if (shu[i] == 0)
			{
				for (int j = i; j <= N; j += i)
				{
					shu[j] = shu[j / i] + 1;
				}
			}
		}

		for (int i = 2; i <= N; i++)
		{
			shu[i] += shu[i - 1];
		}

// 		System.setIn(new FileInputStream("copycat.in"));// 读入文件
//		System.setOut(new PrintStream(new FileOutputStream("copycat.out")));// 输出到文件
//		while (sc.nextToken() != sc.TT_EOF)
		{

			int t = ini();
			while (t-- > 0)
			{
				int a = ini();
				int b = ini();
				out.println(shu[a] - shu[b]);
			}
			out.flush();

		}

	}

	static int gcd(int a, int b)
	{
		return b == 0 ? a : gcd(b, a % b);
	}

	static int ini() throws IOException
	{
		sc.nextToken();
		return (int) sc.nval;
	}

	static long inl() throws IOException
	{
		sc.nextToken();
		return (long) sc.nval;
	}

	static double ind() throws IOException
	{
		sc.nextToken();
		return sc.nval;
	}

	static String ins() throws IOException
	{
		sc.nextToken();
		return sc.sval;
	}

	static String rel() throws IOException
	{
		return in.readLine();
	}

}