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}$