무서운 수

모두가 수와 수학 문제를 좋아합니다. 하지만 할로윈에는 모든 수학 문제가 훨씬 더 무서워진다고 합니다. 오늘의 과제는 무서운 수의 개수를 세는 것입니다.

정수 $x$를 소인수분해했을 때 소인수의 개수(중복 포함)가 정확히 $k$개이면, $x$를 $k$-무서운 수라고 합니다. 이 정의는 아직 무섭게 느껴지지 않을 수 있지만, 문제가 무엇을 묻는지는 아직 보지 않은 것입니다.

$q$개의 질의에 답하세요. 각 질의는 정수 $l$, $r$, $k$로 주어집니다. 질의의 답은 구간 $[l, r]$에 있는 $k$-무서운 수의 개수입니다. 이 문제가 여전히 무섭지 않다면, 모든 $q$개의 질의에 답하세요.

첫 줄에 질의의 개수 $q$가 정수 하나로 주어집니다($1 \le q \le 10^5$). 이어지는 $q$개의 줄에는 공백으로 구분된 자연수 $l_i$, $r_i$, $k_i$가 하나씩 주어집니다. 이는 구간의 양 끝과 $k$-무서운 수 정의에 있는 $k$입니다($2 \le l_i \le r_i \le 10^5$; $1 \le k_i \le 16$).

각 질의마다 구간 $[l_i, r_i]$에 있는 $k_i$-무서운 수의 개수를 한 줄에 하나씩 출력하세요.