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\le K\le 10^{18}$