P4901 Queueing

The formation of Class CYJian... is it a trapezoid?? $\color{white}\text{How many girls can there be in an informatics competition class??}$

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

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 $T$ lines, each containing one positive integer, representing the required beauty.

**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