Reorder Formation Beauty

Problem Description:

In class $CYJian$, the instructor was not impressed with the current formation of the students, so he decided to rearrange the order.

The process is as follows:
1. All students are arranged in a line in increasing order of their student numbers (from $1$ to $N$).
2. Then, repeatedly, from the current line, he picks students at positions corresponding to the Fibonacci sequence: $1,2,3,5,8,13,\dots$ (1-indexed). That is, in each iteration, he extracts the students standing in the $1^{st}$, $2^{nd}$, $3^{rd}$, $5^{th}$, $8^{th}$, $13^{th}$, ... positions of the current line until no valid position can be chosen. These extracted students form one row (preserving their order) and are appended as the next row in the final formation.

For example, if there are 10 students, the process is illustrated below (bold indicates the picked students):

Initial line: 1 2 3 4 5 6 7 8 9 10
After removal, remaining: 4 6 7 9 10

Iteration 2: current line: 4 6 7 9 10
After removal, remaining: 9

Iteration 3: current line: 9

The final formation is:
- Row 1: 1 2 3 5 8
- Row 2: 4 6 7 10
- Row 3: 9

The beauty of a row is defined as the total number of prime factors (with multiplicity) in the prime factorization of the product of all student numbers in that row. (Note: For the number $1$, the count is $0$ because $1$ does not have any prime factors.)

You are given $T$ test cases. For each test case, you are provided with two positive integers $N$ (the number of students) and $K$. Your task is to determine the beauty of the $K$-th row in the final formation. If the final formation contains fewer than $K$ rows, output $-1$.

inputFormat

Input Format:
The first line contains an integer $T$, the number of test cases.
Each of the next $T$ lines contains two space‐separated integers $N$ and $K$, where $N$ is the number of students and $K$ is the row number (1-indexed) to query.

outputFormat

Output Format:
For each test case, output the beauty of the $K$-th row. If the formation has fewer than $K$ rows, output $-1$.

sample

3
10 2
10 3
10 4

7
2
-1