Alice and Bob are studying for their class test together. The topic of the test is Prime Numbers. The preparation is getting too boring for their liking. To make it interesting, they turn it into a game. The winner will get an ice-cream treat from the other.

The game is called Count K-Primes. A number is a $K$-prime if it has exactly $K$ distinct prime factors. The game is quite simple. Alice will give three numbers $A$, $B$ & $K$ to Bob. Bob needs to tell Alice the number of $K$-prime numbers between $A$ & $B$ (both inclusive). If Bob gives the correct answer, he gets a point. If not, Alice gets a point. They play this game $T$ times.

Bob hasn't prepared so well. But he really wants to win the game. He wants you to tell him the correct answer.

------  Input ------

First line of input contains a single integer $T$, the number of times they play. 
Each game is described in a single line containing the three numbers $A$,$B$ & $K$.

------  Output ------

For each game, output on a separate line the number of $K$-primes between $A$ & $B$.

------  Constraints: ------

$1 ≤ T ≤ 10000$  
$2 ≤ A ≤ B ≤ 100000$  
$1 ≤ K ≤ 5$

----- Sample Input 1 ------ 
4
2 5 1
4 10 2
14 15 2
2 20 3
----- Sample Output 1 ------ 
4
2
2
0
----- explanation 1 ------ 
Test case $1$: The range includes $4$ integers $\{2, 3, 4,5 \}$. We need to find the number of integers in this range having only $1$ distinct prime factor.
- For $2$, since it is prime, it has $1$ distinct prime factor.
- For $3$, since it is prime, it has $1$ distinct prime factor.
- For $4$, we can write it as $2\times 2$. Thus, it has $1$ distinct prime factor which is $2$.
- For $5$, since it is prime, it has $1$ distinct prime factor.

Thus, all $4$ integers in the given range are $1$-primes.

Test case $2$: The only *K-primes* in the given range are $6$ and $10$. This is because $6 = 2\times 3$ and $10 = 2\times 5$. Thus both these integers have $2$ distinct prime factors.

Test case $3$: The only *K-primes* in the given range are $14$ and $15$. This is because $14 = 2\times 7$ and $15 = 3\times 5$. Thus both these integers have $2$ distinct prime factors.

Test case $4$: There are no *K-primes* in the given range.

Difficulty: MEDIUM
Tags: Number theory

Dynamic programming

Mathematics
Skill types: Dynamic programming

Starter code:

Solutions:
limit = 100001
prime = [True for _ in range(limit)]
mark = [0 for _ in range(limit)]
for i in range(2, limit):
	if prime[i]:
		mark[i] = 1
		j: int = 2
		while i * j < limit:
			prime[i * j] = False
			mark[i * j] += 1
			j += 1
table = [[0 for _ in range(limit)] for _ in range(6)]
for i in range(2, limit):
	for j in range(1, 6):
		table[j][i] = table[j][i - 1]
	v = mark[i]
	if v >= 1 and v <= 5:
		table[v][i] += 1
t = int(input())
for _ in range(t):
	(a, b, k) = list(map(int, input().split()))
	print(table[k][b] - table[k][a - 1])


max = 10 ** 5 + 1
prime = [1 for i in range(max)]
(prime[0], prime[1]) = (0, 0)
marked = [0 for i in range(max)]
for i in range(2, max):
	if prime[i]:
		marked[i] = 1
		for j in range(i * 2, max, i):
			prime[j] = 0
			marked[j] += 1
count = []
for k in range(1, 6):
	temp = [0] * max
	for i in range(2, max):
		if marked[i] == k:
			temp[i] = temp[i - 1] + 1
		else:
			temp[i] = temp[i - 1]
	count.append(temp)
t = int(input())
for _ in range(t):
	(a, b, k) = map(int, input().split())
	print(count[k - 1][b] - count[k - 1][a - 1])


from sys import stdin, stdout
import bisect
import math

def st():
	return list(stdin.readline().strip())

def inp():
	return int(stdin.readline())

def li():
	return list(map(int, stdin.readline().split()))

def mp():
	return map(int, stdin.readline().split())

def pr(n):
	stdout.write(str(n) + '\n')

def soe(limit):
	l = [1] * (limit + 1)
	prime = []
	for i in range(2, limit + 1):
		if l[i]:
			prime.append(i)
			for j in range(i * i, limit + 1, i):
				l[j] = 0
	return prime

def segsoe(low, high):
	limit = int(high ** 0.5) + 1
	prime = soe(limit)
	n = high - low + 1
	l = [0] * (n + 1)
	for i in range(len(prime)):
		lowlimit = low // prime[i] * prime[i]
		if lowlimit < low:
			lowlimit += prime[i]
		if lowlimit == prime[i]:
			lowlimit += prime[i]
		for j in range(lowlimit, high + 1, prime[i]):
			l[j - low] = 1
	for i in range(low, high + 1):
		if not l[i - low]:
			if i != 1:
				print(i)

def power(a, n):
	r = 1
	while n:
		if n & 1:
			r = r * a
			n = n - 1
		else:
			a = a * a
			n = n >> 1
	return r
l = soe(10 ** 5)
p = [0] * (10 ** 5 + 1)
x = [[0 for i in range(10 ** 5 + 1)] for j in range(6)]
for i in l:
	for j in range(i, 10 ** 5 + 1, i):
		p[j] += 1
for i in range(2, len(p)):
	for j in range(1, 6):
		x[j][i] = x[j][i - 1]
	a = p[i]
	if a >= 1 and a <= 5:
		x[a][i] += 1

def solve():
	(a, b, k) = mp()
	(b, n) = (x[k][a - 1], x[k][b])
	print(n - b)
for _ in range(inp()):
	solve()


def getCount_1(start, end, dp):
	for i in range(2, end + 1):
		if dp[i] == 0:
			for value in range(i, end + 1, i):
				dp[value] += 1
	return dp
testCases = int(input())
result = []
dp = []
for index in range(0, 100001):
	dp.append(0)
dp = getCount_1(2, 100000, dp)
precomputeArray = []
for k in range(6):
	row = []
	count = 0
	for i in range(100001):
		if dp[i] == k:
			count += 1
		row.append(count)
	precomputeArray.append(row)
for testCase in range(testCases):
	inp = input()
	A = int(inp.split(' ')[0])
	B = int(inp.split(' ')[1])
	k = int(inp.split(' ')[2])
	print(precomputeArray[k][B] - precomputeArray[k][A - 1])


N = 100000
omega = [0] * (N + 1)
for p in range(2, N + 1):
	if omega[p] == 0:
		for n in range(p, N + 1, p):
			omega[n] += 1
a = [[] for i in range(6)]
for n in range(1, N + 1):
	if omega[n] < 6:
		a[omega[n]].append(n)
import bisect
for _ in range(int(input())):
	(aa, bb, k) = map(int, input().split())
	print(bisect.bisect_right(a[k], bb) - bisect.bisect_left(a[k], aa))


limit = 100005
ans = [[0 for i in range(0, limit)] for j in range(0, 6)]

def solve():
	primeFactors = [0] * limit
	for i in range(2, limit):
		if primeFactors[i] == 0:
			for j in range(i, limit, i):
				primeFactors[j] += 1
	for i in range(limit):
		if primeFactors[i] < 6:
			ans[primeFactors[i]][i] += 1
	for i in range(6):
		for j in range(1, limit):
			ans[i][j] += ans[i][j - 1]
solve()
T = int(input())
for i in range(T):
	(A, B, K) = map(int, input().split())
	print(ans[K][B] - ans[K][A - 1])


t = int(input())
prime = [0 for i in range(100001)]
p = 2
while p < 100001:
	if prime[p] == 0:
		for j in range(p, 100001, p):
			prime[j] += 1
	p += 1
cp = [[0] * 100001 for i in range(5)]
for i in range(1, 6):
	for j in range(2, 100001):
		if prime[j] == i:
			cp[i - 1][j] = cp[i - 1][j - 1] + 1
		else:
			cp[i - 1][j] = cp[i - 1][j - 1]
while t:
	(a, b, k) = map(int, input().strip().split())
	print(cp[k - 1][b] - cp[k - 1][a - 1])
	t -= 1


import math
factors = [0 for _ in range(pow(10, 5) + 1)]
for i in range(2, pow(10, 5) + 1):
	if factors[i] == 0:
		for j in range(i, pow(10, 5) + 1, i):
			factors[j] += 1
ans = [[factors[0]] for _ in range(5)]
for i in range(5):
	for j in range(1, pow(10, 5) + 1):
		if factors[j] == i + 1:
			ans[i].append(1)
		else:
			ans[i].append(0)
		ans[i][j] += ans[i][j - 1]
T = int(input())
for t in range(T):
	(a, b, x) = map(int, input().split())
	print(ans[x - 1][b] - ans[x - 1][a - 1])


def kprime(a):
	for i in range(2, 100005):
		if a[i][0] == 0:
			a[i][0] = 1
			for j in range(i + i, 100005, i):
				a[j][0] += 1
		if a[i][0] <= 5:
			a[i][a[i][0]] = 1
		for j in range(1, 6):
			a[i][j] += a[i - 1][j]

def solve():
	A = [[0 for x in range(6)] for y in range(100005)]
	kprime(A)
	for _ in range(int(input())):
		(a, b, x) = input().split()
		(a, b, k) = (int(a), int(b), int(x))
		ans = A[b][k] - A[a - 1][k]
		print(ans)
solve()


def sieve(n):
	factors = [0 for _ in range(n + 1)]
	for i in range(2, n + 1):
		if not factors[i]:
			for j in range(2 * i, n + 1, i):
				factors[j] += 1
			factors[i] = 1
	return factors
factors = sieve(100005)
lookup = [[0 for _ in range(100005)] for _ in range(6)]
for i in range(1, 6):
	for j in range(2, 100005):
		if factors[j] == i:
			lookup[i][j] = lookup[i][j - 1] + 1
		else:
			lookup[i][j] = lookup[i][j - 1]
t = int(input())
for _ in range(t):
	(a, b, k) = map(int, input().split())
	print(lookup[k][b] - lookup[k][a - 1])


t = int(input())
import math

def solve():
	limit = 10 ** 5 + 5
	primefactor = [0] * limit
	for i in range(2, limit):
		if primefactor[i] == 0:
			for j in range(i, limit, i):
				primefactor[j] += 1
	global ans
	ans = [[0] * limit for i in range(6)]
	for i in range(limit):
		if primefactor[i] < 6:
			ans[primefactor[i]][i] += 1
	for i in range(6):
		for j in range(1, limit):
			ans[i][j] += ans[i][j - 1]
solve()
while t:
	(a, b, k) = map(int, input().split())
	print(ans[k][b] - ans[k][a - 1])
	t -= 1


lim = 100001

def rmain():
	dp = [0] * lim
	ans = [[0 for _ in range(100001)] for _ in range(6)]
	for i in range(2, lim):
		if dp[i] == 0:
			dp[i] = 1
			for j in range(2 * i, lim, i):
				dp[j] += 1
	for (i, val) in enumerate(dp):
		for j in range(1, 6):
			ans[j][i] = ans[j][i - 1]
		if val <= 5:
			ans[val][i] += 1
	tn = int(input())
	for _ in range(tn):
		(a, b, k) = list(map(int, input().split()))
		print(ans[k][b] - ans[k][a - 1])
rmain()


prime = [True] * 100001
count = [0 for i in range(100001)]
p = 2
while p < 100001:
	if prime[p] == True:
		count[p] += 1
		for i in range(p + p, 100001, p):
			prime[i] = False
			count[i] += 1
	p += 1
k = [[0] * 100001 for i in range(6)]
for i in range(2, 100001, 1):
	if count[i] <= 5:
		k[count[i]][i] = 1
for i in range(6):
	for j in range(2, 100001, 1):
		k[i][j] = k[i][j] + k[i][j - 1]
t = int(input())
for _ in range(t):
	(a, b, r) = map(int, input().split())
	print(k[r][b] - k[r][a - 1])


dp = [0] * 100001
ans = [[0] * 100001 for i in range(6)]
for i in range(2, 100001):
	if dp[i] == 0:
		for x in range(i, 100001, i):
			dp[x] += 1
for i in range(1, 6):
	for j in range(100001):
		if dp[j] == i:
			ans[i][j] = 1
for i in range(1, 6):
	for j in range(1, 100001):
		ans[i][j] += ans[i][j - 1]
t = int(input())
for _ in range(t):
	(a, b, k) = map(int, input().split())
	print(ans[k][b] - ans[k][a - 1])


def primes(top):
	a = [0] * (top + 1)
	for i in range(2, top + 1):
		if a[i] == 0:
			for j in range(i, top + 1, i):
				a[j] += 1
	return a

def get_counts(a, k):
	c = 0
	counts = [0] * len(a)
	for i in range(len(a)):
		if a[i] == k:
			c += 1
		counts[i] = c
	return counts
pr = primes(100000)
m = [get_counts(pr, 1), get_counts(pr, 2), get_counts(pr, 3), get_counts(pr, 4), get_counts(pr, 5)]
for _ in range(int(input())):
	(a, b, k) = [int(x) for x in input().split()]
	print(m[k - 1][b] - m[k - 1][a - 1])


M = 5 + 1
limit = 10 ** 5 + 1
primes = [0 for i in range(limit)]
for x in range(2, limit):
	if primes[x] == 0:
		for y in range(x, limit, x):
			primes[y] += 1
dp = [[0 for k in range(M)] for x in range(limit)]
for x in range(2, limit):
	for y in range(1, M):
		dp[x][y] = dp[x - 1][y]
	y = primes[x]
	if y < M:
		dp[x][y] += 1
for test_case in range(int(input())):
	(A, B, K) = map(int, input().split(' '))
	print(dp[B][K] - dp[A - 1][K])


def sieve(N):
	marked = [0 for i in range(N + 1)]
	isPrime = [True for i in range(N + 1)]
	for i in range(2, N + 1):
		if isPrime[i]:
			marked[i] = 1
			j = 2
			while i * j <= N:
				isPrime[i * j] = False
				marked[i * j] += 1
				j += 1
	return marked

def precompute(marked, N):
	table = [[0 for i in range(10 ** 5 + 1)] for j in range(5)]
	for i in range(2, N + 1):
		for j in range(0, 5):
			table[j][i] = table[j][i - 1]
		v = marked[i]
		if v >= 1 and v <= 5:
			table[v - 1][i] += 1
	return table
marked = sieve(10 ** 5)
table = precompute(marked, 10 ** 5)
T = int(input())
ans = []
for _ in range(T):
	(A, B, K) = [int(i) for i in input().split()]
	ans.append(table[K - 1][B] - table[K - 1][A - 1])
for i in ans:
	print(i)


size = 100000
sieve = [i for i in range(size + 1)]
counts = [0] * (size + 1)
for i in range(2, size + 1):
	if sieve[i] == i:
		counts[i] = 1
		j = i * 2
		while j < size + 1:
			sieve[j] = i
			counts[j] += 1
			j += i
dp = []
mem = {}
for count in counts:
	if count in mem:
		mem[count] += 1
	else:
		mem[count] = 1
	dp.append(mem.copy())

def soln(a, b, k):
	return dp[b].get(k, 0) - dp[a - 1].get(k, 0)
for _ in range(int(input())):
	(a, b, k) = map(int, input().split())
	print(soln(a, b, k))


n = 100000
primefactor = [0 for i in range(n + 1)]
i = 2
lst = []
while i <= n:
	if primefactor[i] == 0:
		primefactor[i] = i
		for j in range(i * i, n + 1, i):
			primefactor[j] = i
	i += 1
for i in range(2, n + 1):
	x = i
	m = {}
	while x != 1:
		if primefactor[x] in m:
			m[primefactor[x]] += 1
		else:
			m[primefactor[x]] = 1
		x = x // primefactor[x]
	lst.append(list(m.items()))
A = [0 for i in range(n + 1)]
prefix = [[0 for k in range(6)] for i in range(n + 1)]
A[0] = 0
A[1] = 1
for i in range(2, n + 1):
	A[i] = len(lst[i - 2])
for i in range(1, n + 1):
	for k in range(1, 6):
		prefix[i][k] = prefix[i - 1][k] + (A[i] == k)
t = int(input())
for _ in range(t):
	(l, r, k) = map(int, input().split())
	print(prefix[r][k] - prefix[l - 1][k])


import math

def rmain():
	li = [0] * 100001
	dp = [[0 for _ in range(100001)] for _ in range(6)]
	for i in range(2, 100001):
		if li[i] == 0:
			li[i] = 1
			for j in range(2 * i, 100001, i):
				li[j] += 1
	for (i, val) in enumerate(li):
		for j in range(1, 6):
			dp[j][i] = dp[j][i - 1]
		if val <= 5:
			dp[val][i] += 1
	tn = int(input())
	for _ in range(tn):
		(a, b, k) = list(map(int, input().split()))
		print(dp[k][b] - dp[k][a - 1])
	return
rmain()


(sieve, cnt, d) = ([1] * 100001, [0] * 100001, [[0, 0] for _ in range(6)])
sieve[0] = sieve[1] = 0
for i in range(2, 100001):
	if sieve[i]:
		cnt[i] += 1
		for j in range(i * 2, 100001, i):
			(sieve[j], cnt[j]) = (0, cnt[j] + 1)
for i in range(1, 6):
	for j in range(2, 100001):
		d[i].append(d[i][-1] + (cnt[j] == i))
for _ in range(int(input())):
	(a, b, k) = map(int, input().split())
	print(d[k][b] - d[k][a - 1])


def kprime(n):
	s = [0 for b in range(n + 1)]
	for i in range(2, n + 1):
		if not s[i]:
			for j in range(2 * i, n + 1, i):
				s[j] += 1
			s[i] = 1
	return s
s = kprime(100005)
t = [[0 for b in range(100005)] for b in range(6)]
for i in range(1, 6):
	for j in range(2, 100005):
		if s[j] == i:
			t[i][j] = t[i][j - 1] + 1
		else:
			t[i][j] = t[i][j - 1]
T = int(input())
for b in range(T):
	(A, B, K) = map(int, input().split())
	print(t[K][B] - t[K][A - 1])


from math import *
R = lambda : list(map(int, input().split()))
M = 100001
sieve = [0] * M
(sieve[0], sieve[1]) = (0, 0)
for i in range(2, M):
	if sieve[i] == 0:
		for j in range(i, M, i):
			sieve[j] += 1
m = [[0 for j in range(M)] for i in range(6)]
for i in range(1, 6):
	for j in range(1, M):
		if sieve[j] == i:
			m[i][j] = 1
		m[i][j] += m[i][j - 1]

def main():
	for _ in range(int(input())):
		(A, B, K) = R()
		print(m[K][B] - m[K][A - 1])
main()


lim = 100001
dp = [0] * lim
for i in range(2, lim):
	if dp[i] == 0:
		dp[i] = 1
		for j in range(2 * i, lim, i):
			dp[j] += 1
ans = [[0] * lim for i in range(6)]
for i in range(lim):
	if dp[i] <= 5:
		ans[dp[i]][i] += 1
for i in range(6):
	for j in range(1, lim):
		ans[i][j] += ans[i][j - 1]
for _ in range(int(input())):
	(a, b, k) = map(int, input().split())
	print(ans[k][b] - ans[k][a - 1])


lim = 10 ** 5 + 1
dp = [0] * lim
for i in range(2, lim):
	if dp[i] == 0:
		for j in range(i, lim, i):
			dp[j] += 1
nk = [['X']]
for k in range(1, 5 + 1):
	l = [0] * lim
	for j in range(lim):
		if dp[j] == k:
			l[j] = l[j - 1] + 1
		else:
			l[j] = l[j - 1]
	nk.append(l)
t = int(input())
for _ in range(t):
	(a, b, k) = map(int, input().split())
	print(nk[k][b] - nk[k][a - 1])


from bisect import bisect_left, bisect_right
import math
from sys import maxsize
from collections import defaultdict
from bisect import bisect_left
from heapq import heapify, heappush, heappop
from collections import deque
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]

def sieve(n):
	fac = [0 for _ in range(n + 1)]
	for i in range(2, n + 1):
		if not fac[i]:
			for j in range(2 * i, n + 1, i):
				fac[j] += 1
			fac[i] = 1
	return fac
f = sieve(100005)
lookup = [[0 for _ in range(100005)] for _ in range(6)]
for i in range(1, 6):
	for j in range(2, 100005):
		if f[j] == i:
			lookup[i][j] = lookup[i][j - 1] + 1
		else:
			lookup[i][j] = lookup[i][j - 1]
for _ in range(ii()):
	(a, b, k) = il()
	print(lookup[k][b] - lookup[k][a - 1])


n = 10 ** 5 + 1
prime = [0] * n
for i in range(2, n):
	if prime[i] == 0:
		for j in range(i, n, i):
			prime[j] += 1
k_prime = {}
for i in range(1, 6):
	k_prime[i] = [0] * n
	for j in range(2, n):
		if prime[j] == i:
			k_prime[i][j] += 1
		k_prime[i][j] += k_prime[i][j - 1]
for _ in range(int(input())):
	(a, b, k) = map(int, input().split())
	t_1 = k_prime[k][b] - k_prime[k][a - 1]
	print(t_1)


n = 10 ** 5 + 1
l = [0] * n
for i in range(2, n):
	if l[i] == 0:
		for j in range(i, n, i):
			l[j] += 1
x = [0]
for k in range(1, 6):
	m = [0] * n
	for i in range(2, n):
		if l[i] == k:
			m[i] += 1
		m[i] += m[i - 1]
	x.append(m)
t = int(input())
while t > 0:
	(a, b, k) = map(int, input().split())
	ans = x[k][b] - x[k][a - 1]
	print(ans)
	t -= 1


import math
size = 100000
prime = [True] * (size + 1)
counts = [0] * (size + 1)
prime[0] = False
prime[1] = False
for i in range(2, 100001):
	if prime[i] == True:
		counts[i] = 1
		for j in range(2 * i, 100001, i):
			prime[j] = False
			counts[j] += 1
dp = []
mem = {}
for count in counts:
	if count in mem:
		mem[count] += 1
	else:
		mem[count] = 1
	dp.append(mem.copy())

def soln(a, b, k):
	return dp[b].get(k, 0) - dp[a - 1].get(k, 0)
for _ in range(int(input())):
	(a, b, k) = map(int, input().split())
	print(soln(a, b, k))


n = 10 ** 5 + 2

def Sieve(n):
	(prime, p) = ([0 for i in range(n)], 2)
	for i in range(2, n):
		if prime[i] == 0:
			for j in range(p, n, p):
				prime[j] += 1
		p += 1
	return prime

def array():
	(a, q, l) = ([True for i in range(6)], [], Sieve(n))
	for i in range(n):
		a = a[:]
		if l[i] <= 5:
			a[l[i]] += 1
		q.append(a)
	return q
q = array()
for _ in range(int(input())):
	(a, b, k) = map(int, input().split())
	print(q[b][k] - q[a - 1][k])


M = 6
U = 100001
dp = [[0] * M]
for x in range(1, U):
	dp += [[0] * M]
	for y in range(M):
		dp[x][y] = dp[x - 1][y]
	p = 2
	q = x
	y = 0
	while p * p <= q and y < M:
		if q % p == 0:
			q /= p
			y += 1
			while q % p == 0:
				q /= p
		p += 1
	if q > 1 and y < M:
		y += 1
	if y < M:
		dp[x][y] += 1
for test_case in range(int(input())):
	(A, B, K) = map(int, input().split(' '))
	print(dp[B][K] - dp[A - 1][K])


LIMIT = 100001
prime = [True] * LIMIT
count = [0] * LIMIT
for i in range(2, LIMIT):
	if prime[i]:
		for j in range(i, LIMIT, i):
			prime[j] = False
			count[j] += 1
mat = [[0] * LIMIT for i in range(6)]
for i in range(2, LIMIT):
	for j in range(1, 6):
		mat[j][i] = mat[j][i - 1]
	c = count[i]
	if c < 6:
		mat[c][i] += 1

def main():
	T = int(input())
	for i in range(T):
		(low, high, k) = map(int, input().split())
		print(mat[k][high] - mat[k][low - 1])
main()


import math
primes = [0] * 100001
for i in range(2, 100001):
	if primes[i] == 0:
		for j in range(i, 100001, i):
			primes[j] += 1
count = []
for k in range(1, 6):
	c = [0] * 100001
	for i in range(100001):
		if primes[i] == k:
			c[i] = c[i - 1] + 1
		else:
			c[i] = c[i - 1]
	count.append(c)
T = int(input())
for _ in range(T):
	(a, b, k) = map(int, input().split())
	print(count[k - 1][b] - count[k - 1][a - 1])


test = int(input())
t1 = [0]
t2 = [0]
t3 = [0]
t4 = [0]
t5 = [0]
n = 100000
l = n + 1
prime = [0 for i in range(0, l)]
for p in range(2, n):
	if prime[p] == 0:
		for i in range(p, l, p):
			prime[i] += 1
for i in range(1, 100001):
	s = prime[i]
	if s == 1:
		t1.append(t1[i - 1] + 1)
		t2.append(t2[i - 1])
		t3.append(t3[i - 1])
		t4.append(t4[i - 1])
		t5.append(t5[i - 1])
	elif s == 2:
		t1.append(t1[i - 1])
		t2.append(t2[i - 1] + 1)
		t3.append(t3[i - 1])
		t4.append(t4[i - 1])
		t5.append(t5[i - 1])
	elif s == 3:
		t1.append(t1[i - 1])
		t2.append(t2[i - 1])
		t3.append(t3[i - 1] + 1)
		t4.append(t4[i - 1])
		t5.append(t5[i - 1])
	elif s == 4:
		t1.append(t1[i - 1])
		t2.append(t2[i - 1])
		t3.append(t3[i - 1])
		t4.append(t4[i - 1] + 1)
		t5.append(t5[i - 1])
	elif s == 5:
		t1.append(t1[i - 1])
		t2.append(t2[i - 1])
		t3.append(t3[i - 1])
		t4.append(t4[i - 1])
		t5.append(t5[i - 1] + 1)
	else:
		t1.append(t1[i - 1])
		t2.append(t2[i - 1])
		t3.append(t3[i - 1])
		t4.append(t4[i - 1])
		t5.append(t5[i - 1])
for tt in range(test):
	(a, b, k) = map(int, input().split())
	if k == 1:
		print(t1[b] - t1[a - 1])
	if k == 2:
		print(t2[b] - t2[a - 1])
	if k == 3:
		print(t3[b] - t3[a - 1])
	if k == 4:
		print(t4[b] - t4[a - 1])
	if k == 5:
		print(t5[b] - t5[a - 1])


P = input
J = int
E = len
D = range
B = [None] * 100001
L = []
for A in D(2, E(B)):
	B[A] = set()
for A in D(2, 100001):
	if E(B[A]) != 0:
		continue
	L.append(A)
	B[A].add(A)
	for F in D(2, E(B)):
		G = F * A
		if G > 100000:
			break
		else:
			while G <= 100000:
				B[G].add(A)
				G *= A
C = [[0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0]]
K = [0, 0, 0, 0, 0, 0]
for A in D(2, E(B)):
	for F in D(1, E(C)):
		C[F].append(K[F])
	H = E(B[A])
	if H <= 5:
		C[H][-1] += 1
		K[H] += 1
M = J(P())
for Q in D(1, M + 1):
	I = P().split(' ')
	N = J(I[0])
	O = J(I[1])
	type = J(I[2])
	print(f'{C[type][O] - C[type][N - 1]}')


t = int(input())
n = 100000
marked = [0] * (n + 1)
primes = [True] * (n + 1)
for i in range(2, n + 1):
	if primes[i]:
		marked[i] = 1
		for j in range(2 * i, n + 1, i):
			marked[j] += 1
			primes[j] = False
table = [[0] * (n + 1) for i in range(6)]
for i in range(2, n + 1):
	for j in range(1, 6):
		table[j][i] = table[j][i - 1]
	v = marked[i]
	if v < 6:
		table[v][i] += 1
for _ in range(t):
	(a, b, k) = map(int, input().split())
	print(table[k][b] - table[k][a - 1])


def PrimeFactorCountSieve(n):
	pfc = [0] * (n + 1)
	for i in range(2, n + 1):
		if pfc[i] == 0:
			for j in range(i, n + 1, i):
				pfc[j] += 1
	return pfc

def CumulativeKPrimeFactorCount(pfc):
	ckpfc = [[0 for _ in range(6)] for __ in range(len(pfc))]
	for a in range(2, len(ckpfc)):
		if pfc[a] < 6:
			ckpfc[a][pfc[a]] = 1
		for b in range(6):
			ckpfc[a][b] += ckpfc[a - 1][b]
	return ckpfc
_MAX = 100000
pfc = PrimeFactorCountSieve(_MAX)
ckpfc = CumulativeKPrimeFactorCount(pfc)
for case in range(int(input())):
	(a, b, k) = tuple(map(int, input().split()))
	print(ckpfc[b][k] - ckpfc[a - 1][k])


factors = [0 for i in range(100001)]
p = 2
while p < 100001:
	if factors[p] == 0:
		for j in range(p, 100001, p):
			factors[j] += 1
	p += 1
dp = [[0 for b in range(100001)] for b in range(6)]
for i in range(1, 6):
	for j in range(2, 100001):
		if factors[j] == i:
			dp[i][j] = dp[i][j - 1] + 1
		else:
			dp[i][j] = dp[i][j - 1]
tt = int(input())
for b in range(tt):
	(a, b, k) = map(int, input().split())
	print(dp[k][b] - dp[k][a - 1])


def eve(N):
	m = [0 for i in range(N + 1)]
	Prime = [True for i in range(N + 1)]
	for i in range(2, N + 1):
		if Prime[i]:
			m[i] = 1
			j = 2
			while i * j <= N:
				Prime[i * j] = False
				m[i * j] += 1
				j += 1
	return m

def pre_comp(m, N):
	table = [[0 for i in range(10 ** 5 + 1)] for j in range(5)]
	for i in range(2, N + 1):
		for j in range(0, 5):
			table[j][i] = table[j][i - 1]
		v = m[i]
		if v >= 1 and v <= 5:
			table[v - 1][i] += 1
	return table
m = eve(10 ** 5)
table = pre_comp(m, 10 ** 5)
T = int(input())
ans = []
for _ in range(T):
	(A, B, K) = [int(i) for i in input().split()]
	ans.append(table[K - 1][B] - table[K - 1][A - 1])
for i in ans:
	print(i)


limit = 10 ** 5 + 1
dp = [0 for i in range(limit)]
for i in range(2, limit):
	if dp[i] != 0:
		continue
	for j in range(i, limit, i):
		dp[j] += 1
ans = [[0 for i in range(limit)] for j in range(6)]
for i in range(2, limit):
	if dp[i] <= 5:
		ans[dp[i]][i] = 1
for i in range(1, 6):
	for j in range(2, limit):
		ans[i][j] += ans[i][j - 1]
t = int(input())
while t:
	(a, b, k) = map(int, input().split(' '))
	print(ans[k][b] - ans[k][a - 1])
	t -= 1


arr = [[i] for i in range(10 ** 5 + 1)]
dictionary = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0}
prime_factors_arr = [[0] * 6 for i in range(10 ** 5 + 1)]
for i in range(2, 10 ** 5 + 1):
	pos = i
	if len(arr[i]) == 1:
		while pos <= 10 ** 5:
			arr[pos].append(i)
			pos += i
	if len(arr[i]) - 1 <= 5:
		dictionary[len(arr[i]) - 1] += 1
	temp = [0] * 6
	for j in range(1, 6):
		temp[j] = dictionary[j]
	prime_factors_arr[i] = temp
tests = int(input())
for i in range(tests):
	(a, b, k) = map(int, input().split())
	ans = prime_factors_arr[b][k] - prime_factors_arr[a - 1][k]
	print(ans)


from bisect import *
n = 100001
a = [0] * n
for i in range(2, n, 2):
	a[i] += 1
for i in range(3, n, 2):
	if a[i] == 0:
		for j in range(i, n, i):
			a[j] += 1
q = {i: [] for i in range(1, 6)}
for i in range(n):
	if 0 < a[i] < 6:
		q[a[i]].append(i)
for _ in range(int(input())):
	(a, b, k) = map(int, input().split())
	print(bisect_right(q[k], b) - bisect_left(q[k], a))


dp = [[0 for row in range(6)] for col in range(100001)]

def sieve():
	for i in range(2, 100001):
		if dp[i][0] == 0:
			dp[i][0] = 1
			for j in range(2 * i, 100001, i):
				dp[j][0] += 1
		if dp[i][0] <= 5:
			dp[i][dp[i][0]] = 1
		for j in range(1, 6):
			dp[i][j] += dp[i - 1][j]
sieve()
for t in range(int(input())):
	(A, B, K) = map(int, input().split())
	print(dp[B][K] - dp[A - 1][K])


import numpy as np

def generateTable():
	N = 100000 - 1
	dp = np.zeros(N)
	for i in range(N):
		if not dp[i]:
			j = i
			while j < N:
				dp[j] += 1
				j += i + 2
	return dp

def findAll(a, b, k, dp):
	return (dp[a - 2:b - 2 + 1] == k).sum()

def main():
	dp = generateTable()
	for _ in range(int(input())):
		(a, b, k) = map(int, input().split())
		ans = findAll(a, b, k, dp)
		print(ans)
main()


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
from collections import defaultdict
MAX_N = 10 ** 5 + 1

def dfactors():
	factors = [0] * MAX_N
	p = 2
	while p < MAX_N:
		if factors[p] == 0:
			for i in range(p, MAX_N, p):
				factors[i] += 1
		p += 1
	return factors

def prefix_sum(data):
	pre = defaultdict(list)
	pre[0] = [0] * 6
	for i in range(1, MAX_N):
		pre[i] = pre[i - 1][:]
		k = factors[i]
		if 1 <= k <= 5:
			pre[i][k] += 1
	return pre
factors = dfactors()
pre = prefix_sum(factors)
for _ in range(int(input())):
	(A, B, K) = map(int, input().split())
	print(pre[B][K] - pre[A - 1][K])


def number_of_prime_factors(limit, k):
	number_of_prime_factors = [1, 0] * (limit // 2 + 1)
	number_of_prime_factors[:3] = [0, 0, 1]
	p = 3
	while p <= limit:
		if not number_of_prime_factors[p]:
			for i in range(p, limit + 1, p):
				number_of_prime_factors[i] += 1
		p += 2
	k_factors = {i: [0] for i in range(1, k + 1)}
	for i in range(2, limit + 1):
		try:
			k_factors[number_of_prime_factors[i]].append(i)
		except KeyError:
			pass
	return k_factors

def tr():
	return range(int(line()))
from bisect import bisect_left, bisect_right

def main():
	k_factors = number_of_prime_factors(100000, 5)
	for _ in range(int(input())):
		(a, b, k) = map(int, input().split())
		low = bisect_left(k_factors[k], a)
		high = bisect_right(k_factors[k], b)
		print(high - low)
main()


t = int(input())
n = 100000
prime = [0 for i in range(n + 1)]
p = 2
while p <= n:
	if not prime[p]:
		for j in range(p, n + 1, p):
			prime[j] += 1
	p += 1
cache = [[0 for i in range(n + 1)] for j in range(5)]
for i in range(1, 6):
	for j in range(2, n + 1):
		if prime[j] == i:
			cache[i - 1][j] = cache[i - 1][j - 1] + 1
		else:
			cache[i - 1][j] = cache[i - 1][j - 1]
while t:
	(A, B, K) = map(int, input().split())
	print(cache[K - 1][B] - cache[K - 1][A - 1])
	t -= 1


val = 10 ** 5
ans = [0] * (val + 1)
for i in range(2, val + 1):
	if ans[i] == 0:
		for j in range(i, val + 1, i):
			ans[j] += 1
k = [[0 for _ in range(val + 1)] for _ in range(5)]
for i in range(2, val + 1):
	if ans[i] <= 5:
		k[ans[i] - 1][i] = 1
f = []
for i in range(5):
	temp = [0]
	for j in range(1, val + 1):
		temp.append(k[i][j] + temp[-1])
	f.append(temp)
for _ in range(int(input())):
	(a, b, k) = map(int, input().split())
	print(f[k - 1][b] - f[k - 1][a - 1])


from math import *
R = lambda : list(map(int, input().split()))
MAX = 100000 + 1
sieve = [0] * MAX
(sieve[0], sieve[1]) = (0, 0)
for i in range(2, MAX):
	if sieve[i] == 0:
		for j in range(i, MAX, i):
			sieve[j] += 1
m = [[0 for j in range(MAX)] for i in range(5 + 1)]
for i in range(1, 6):
	for j in range(1, MAX):
		if sieve[j] == i:
			m[i][j] = 1
		m[i][j] += m[i][j - 1]
for _ in range(int(input())):
	(a, b, k) = R()
	res = m[k][b] - m[k][a - 1]
	print(res)