import java.util.Scanner;
import java.io.File;
import java.io.PrintWriter;
import java.lang.Math;
import java.math.BigInteger;


/**
 * Created by IntelliJ IDEA.
 * User: m09fpv
 * Date: 02.12.2009
 * Time: 19:21:50
 * To change this template use File | Settings | File Templates.
 */
public class rvq {
  public static void main(String[]  args) throws Exception {
   Scanner in=new  Scanner(new File("rvq.in"));
   PrintWriter out=new PrintWriter(new File("rvq.out"));
   long[] a=new long[262144];
   long[] b=new long[262144];
   long[] c=new long[262144];
   int x,y; long res,res2,tmp,tmp2;
   for(int i=1;i<131072;i++){
     tmp=i%23456;
     tmp2=i%12345;
    a[i]=((tmp2*tmp2)%12345)+(tmp*tmp*tmp)%23456;
    b[i+131072]=a[i];
    c[i+131072]=a[i];
    for(int j=(i+131072)>>1;j>0;j=j>>=1){
      b[j]=Math.min(b[2*j],b[2*j+1]);
      c[j]=Math.max(c[2*j],c[2*j+1]);
    }
   }
  // for(int i=0;i<262143;i++){out.println(b[i]); }
   int k=in.nextInt();
    for(int i=0;i<k;i++){
     x=in.nextInt();
     y=in.nextInt();
      if(x>0){
       res=1000000000;
       res2=-1000000000;
        x=x+131072; y=y+131072;
       while(x<=y){
         if(x%2==1){
           res=Math.min(res,b[x]);
           res2=Math.max(res2,c[x]); x++;
         }
         if(y%2==0){
           res=Math.min(res,b[y]);
           res2=Math.max(res2,c[y]);  y--;
         }
        x>>=1; y>>=1;
       }
       out.println(res2-res);
       //out.println(res2+" "+res);
    }
     if(x<0){
       x=Math.abs(x); b[x+131072]=y; c[x+131072]=y;
        for(int j=(x+131072)/2;j>0;j=j/2){
         b[j]=Math.min(b[2*j],b[2*j+1]);
         c[j]=Math.max(c[2*j],c[2*j+1]);
         }
      }
    }
   in.close();
   out.close();
 }
}
