31247번 - 2024는 무엇이 특별할까?

문제

백준 온라인 저지의 신년대회 Hello, BOJ 2024!의 개최일은 2024년 1월 14일이다. 정휘는 대회가 개최된다는 사실이 기뻐 제목을 뚫어져라 보다가 2024가 무언가 특별하다는 사실을 깨달았다.

그렇다. $\tau_o(n)$을 n의 약수이면서 홀수인 양의 정수의 개수, $\tau_e(n)$을 $n$의 약수이면서 짝수인 양의 정수의 개수라고 할 때, $\tau_e(2024) =3\tau_o(2024)$을 만족한다. 다음에 이런 연도가 오려면 16년 뒤인 2040년이 되어야 한다.

$\tau_e(x) =K\times\tau_o(x)$를 만족하는 양의 정수 $x$를 $K$-특별한 수라고 정의하자. 양의 정수 $N$과 음이 아닌 정수 $K$가 주어진다. $N$ 이하의 양의 정수 중 $K$-특별한 수의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

이후 $T$개의 줄에 걸쳐 테스트 케이스가 한 줄에 하나씩 주어진다. 각 테스트 케이스는 한 줄로 구성되어 있으며, 각각 양의 정수 $N$과 음이 아닌 정수 $K$가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스마다, 한 줄에 하나씩 $N$ 이하의 양의 정수 중 $K$-특별한 수의 개수를 출력한다.

제한

• 1ドル\le T\le 100,円 000$
• 1ドル\le N\le 10^{18}$
• 0ドル\leq K\leq 10^{18}$

힌트