Problem: Maxim has got a calculator. The calculator has two integer cells. Initially, the first cell contains number 1, and the second cell contains number 0. In one move you can perform one of the following operations:

  1. Let's assume that at the current time the first cell contains number a, and the second cell contains number b. Write to the second cell number b + 1; 
  2. Let's assume that at the current time the first cell contains number a, and the second cell contains number b. Write to the first cell number a·b. 



Maxim is wondering, how many integers x (l ≤ x ≤ r) are there, such that we can write the number x to the first cell of the calculator, having performed at most p moves.

Input

The first line contains three integers: l, r, p (2 ≤ l ≤ r ≤ 109, 1 ≤ p ≤ 100). 

The numbers in the line are separated by single spaces.

Output

In a single line print a single integer — the answer to the problem.

Examples

Input

2 10 3


Output

1


Input

2 111 100


Output

106


Input

2 111 11


Output

47

Solution (in JAVA):

Solution:
import java.io.OutputStreamWriter;
import java.io.BufferedWriter;
import java.io.PrintStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Random;
import java.io.Writer;
import java.util.Collection;
import java.util.List;
import java.util.BitSet;
import java.io.IOException;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.TreeSet;
import java.math.BigInteger;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author ogiekako
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		MyScanner in = new MyScanner(inputStream);
		MyPrintWriter out = new MyPrintWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
    // 2944730
    int[] primes;
    int[] candidates;
    int numCandidates;
    public void solve(int testNumber, MyScanner in, MyPrintWriter out) {
        int N = (int) 1e9;
        int L = in.nextInt(), R = in.nextInt();
        int p = in.nextInt();
        if(p<3){
            out.println(0);return;
        }
        primes = MathUtils.generatePrimes(p + 1);
        candidates = new int[2944730];
        Arrays.fill(candidates, Integer.MAX_VALUE);
        numCandidates = 0;
        gen(0, 1L, N);
        Arrays.sort(candidates);
        int[] dist = new int[numCandidates];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;// 1
        boolean[] answer = new boolean[numCandidates];
        answer[0] = true;
        for(int n=2;n<=p;n++){
            for (int i = 0, j = 0; i < dist.length; i++)if(dist[i] < p - n && candidates[i] <= N/n){
                int nxt = candidates[i] * n;
                while(candidates[j] != nxt)j++;
                if(dist[j] > dist[i] + 1){
                    dist[j] = dist[i] + 1;
                    answer[j] = true;
                }
            }
        }
        int res = 0;
        for (int i = 0; i < answer.length; i++)if(answer[i] && L <= candidates[i] && candidates[i] <= R)res++;
        out.println(res);
    }

    private void gen(int p, long number, int N) {
        if (p >= primes.length) {
            candidates[numCandidates++] = (int) number;
            return;
        }
        while (number <= N) {
            gen(p + 1, number, N);
            number *= primes[p];
        }
    }
}

class MyScanner {
    private final InputStream in;

    public MyScanner(InputStream in) {
        this.in = in;
    }

    int bufLen;
    int bufPtr;
    byte[] buf = new byte[1024];

    public int read() {
        if (bufLen == -1)
            throw new InputMismatchException();
        if (bufPtr >= bufLen) {
            bufPtr = 0;
            try {
                bufLen = in.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (bufLen <= 0)
                return -1;
        }
        return buf[bufPtr++];
    }

    public int nextInt() {
        try {
            int c = read();
            if (c == -1) return c;
            while (c != '-' && (c < '0' || '9' < c)) {
                c = read();
                if (c == -1) return c;
            }
            if (c == '-') return -nextInt();
            int res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while ('0' <= c && c <= '9');
            return res;
        } catch (Exception e) {
            return -1;
        }
    }


    }

class MyPrintWriter {
    PrintWriter out;

    public MyPrintWriter(OutputStream outputStream) {
        out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public MyPrintWriter(Writer writer) {
        out = new PrintWriter(writer);
    }

    public void println(Object... os) {
        for (int i = 0; i < os.length - 1; i++) {
            out.print(os[i]);
            out.print(' ');
        }
        out.println(os[os.length - 1]);
    }

    public void close() {
        out.close();
    }

    }

class MathUtils {

    public static int[] generatePrimes(int upTo) {
        int N = upTo;
        boolean[] isPrime = generatePrimaryTable(N);
        int m = 0;
        for (boolean p : isPrime) if (p) m++;
        int[] res = new int[m];
        m = 0;
        for (int i = 0; i < isPrime.length; i++) {
            if (isPrime[i]) res[m++] = i;
        }
        return res;
    }

    public static boolean[] generatePrimaryTable(int n) {
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, true);
        if (0 < n) isPrime[0] = false;
        if (1 < n) isPrime[1] = false;
        for (int i = 2; i * i < n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j < n; j += i)
                    isPrime[j] = false;
            }
        }
        return isPrime;
    }

    }