위험 지수 구하기
시간 제한0.2초메모리 제한512 MB
N 이하의 정수 중 소인수가 모두 K 이하인 수의 개수를 구합니다. N, K는 100000 이하이고 질의는 50000개입니다.
문제
대형 투자 은행에서 일하는 엔지니어들은 새 암호 알고리즘을 시험하기 위해 그 알고리즘의 위험 지수(Risk Factor)라는 값을 계산해야 한다. 간단히 말해, 위험 지수는 어떤 값 N 이하의 수 중에서 어떤 값 K보다 큰 소수의 배수가 아닌 수의 개수이다.
더 엄밀하게, 값 N과 K가 주어졌을 때 위험 지수는 다음 집합의 원소 개수이다.
{x such that 2 ≤ x ≤ N and for every prime divisor p of x, p ≤ K}
엔지니어들은 여러 N과 K에 대해 위험 지수를 계산해야 하며, 여러분에게 답할 질의 집합을 준비했다. 도와줄 수 있는가?
입력
첫째 줄에 엔지니어들이 준비한 질의의 수 Q (1 ≤ Q ≤ 5 × 104)가 주어진다. 다음 Q개의 줄 각각에는 두 정수 N과 K (2 ≤ N, K ≤ 105)가 주어진다.
출력
Q개의 줄을 출력한다. 각 줄에는 입력의 해당 질의에 대한 위험 지수를 정수로 출력한다.