# This script essentially uses ideas of Giovanni Resta.
# Many thanks to him for sharing them!
def rebase(x):
    """Does rebasing of x from base b to base q.

       For any natural number x, returns the one whose base q representation 
       is by the same sequence of digits as the base b representation of x.
       """
    u,y,i=x,0,0
    while u>0:
        y=y+multiplied_q_to[i][u%b]
        u,i=u//b,i+1
    return y
def some_between(left,right):
    """Looks for a number n between left and right such that rebase(n) is a multiple of n.

    For any positive integers left and right with left<=right, returns some integer n such that left<=n<=rb 
    and rebase(n) is a multiple of n, if such an n exists, otherwise returns 0.
    """
    Left=rebase(left)
    if Left%left==0:
        z=left
    else:
        if left==right:
            z=0
        else:   
            Right=rebase(right)
            if Right%right==0:
                z=right
            else:
                st,z=[(left,Left)],0
                st.append((right,Right))
                while len(st)>1:
                    l,L,r,R=st[0][0],st[0][1],st[1][0],st[1][1]
                    if (L//r==R//l) or (r==l+1):
                        st[0:1]=[]
                    else:
                        new=(l+r)//2
                        New=rebase(new)
                        if New%new==0:
                            z=new
                            st[:]=[]
                        else:
                            st[0:2]=[st[0],(new,New),st[1]]
    return z
def least_between(left,right):
    """Looks for the least n between left and right such that rebase(n) is a multiple of n.

    For any positive integers left and right with left<=right, returns the least integer n such that 
    left<=n<=rb and rebase(n) is a multiple of n, if such an n exists, otherwise returns 0.
    """
    if rebase(left)%left==0:
        z=left
    else:
        y=some_between(left,right)
        if y>0:
            while y>0:
                z=y
                y=some_between(left,y-1)
        else:
            z=0
    return z
def all_between(left,right):
    """Consecutively prints all n between left and right such that rebase(n) is a multiple of n."""
    z,i=left,s+1
    while z<right:
        z1=least_between(z,right)
        if z1>0:
            print(str(i)+" "+str(z1))
            i=i+1
            z=z1+1
        else:
            z=right
b,q,m,M,s=2,6,0,10**7,1
multiplied_q_to,i=[],0
while b**i<M-1:
    v=[]    
    for k in range(b):
        v.append(k*q**i)
    multiplied_q_to.append(v)
    i=i+1
print(str(s)+" 0")
all_between(1,M-1)