Background

The formation of Class CYJian... is it a trapezoid??

$\color{white}\text{How many girls can there be in an informatics competition class??}$

Problem Description

The instructor thinks that Class CYJian’s formation is not very good-looking very bad-looking, so the instructor decides to rearrange it.

First, the instructor asks all students to line up in increasing order of student ID in a single row. Then, each time, the instructor pulls out the $1, 2, 3, 5, 8, 13, \cdots$-th people (roughly the Fibonacci sequence) from the current queue, until no one can be pulled out. These selected people form a new row, which is placed behind the previous row.

For example, if there are $10$ students, it goes like this (bold means the currently selected person):

1. $\bm{\color{red}1}\ \bm{\color{red}2}\ \bm{\color{red}3}\ 4 \ \bm{\color{red}5} \ 6 \ 7 \ \bm{\color{red}8} \ 9\ 10$, after taking them away: $4\ 6\ 7\ 9\ 10$;
2. $\bm{\color{red}4}\ \bm{\color{red}6}\ \bm{\color{red}7}\ 9\ \bm{\color{red}10}$, after taking them away: $9$;
3. $\bm{\color{red}9}$.

The final formation looks like this:

• Row 1: $1\ 2\ 3\ 5\ 8$;
• Row 2: $4\ 6\ 7\ 10$;
• Row 3: $9$.

(Of course, a formation arranged by the instructor has to be said to look good...)

Now we define the “beauty” of a row as the number of prime factors in the prime factorization of the product of all student IDs in that row. In particular, since $1$ cannot be decomposed into any prime factors, its count is $0$.

For example, for the second row, $4 \times 6 \times 7 \times 10=1680=2 \times 2 \times 2 \times 2 \times 3 \times 5 \times 7$, so the beauty of this row is $7$.

There are $T$ classes in the grade, and each class must be arranged once. For the $i$-th class, you are given the number of students $N_i$ and a positive integer $K_i$. You need to find the beauty of the $K_i$-th row after arranging the formation for the $i$-th class.

In particular, if the formation does not have a $K_i$-th row, output $-1$.

Input Format

The first line contains a positive integer $T$.

The next $T$ lines each contain two positive integers $N_i$ and $K_i$.

The meanings of the variables are described in the statement.

Output Format

Output $T$ lines, each containing one positive integer, representing the required beauty.

3
10 2
12 2
1 2

7
7
-1

Hint

This problem uses bundled testdata.

• Subtask 1 (30pts): $K_i = 1$, $1 \le N_i, T \le 1000$;
• Subtask 2 (30pts): $1 \le K_i \le 100$, $1 \le N_i \le 10000$, $1 \le T \le 5000$;
• Subtask 3 (40pts): $1 \le K_i \le 10000$, $1 \le N_i \le 5 \times 10^6$, $1 \le T \le 10^6$.

The testdata does not guarantee the existence of a test point where all outputs are $-1$.

Translated by ChatGPT 5