Question
Power Surge
Bob is competing in a mage’s trial with an initial power level of X. Each second, he finds the smallest prime factor of his current power level and adds it to his total. He aims to reach or surpass a target power level of Y as fast as possible. Find the minimum time in seconds required for Bob to succeed.
Input
The first line of input contains a single integer T, denoting the number of test cases
Each test case consists of a single line containing two integers X and Y, the initial and required score of Lina.
Constraints
1 ≤ T ≤ 1000
2 ≤ X ≤ 10
20 ≤ Y ≤ 109
Each test case consists of a single line containing two integers X and Y, the initial and required score of Lina.
Constraints
1 ≤ T ≤ 1000
2 ≤ X ≤ 10
20 ≤ Y ≤ 109
Output
For each test case, output the minimum time in seconds, after which Lina's score becomes ≥ Y
Example
Sample Input
2
2 23
9 20
Sample Output
11
5
Explanation
Test case 1: The initial score is 2. Lina needs the score to be at least 23.
The smallest prime factor of 2 is 2. Thus, the score increase to 2 + 2 = 4.
The smallest prime factor of 4 is 2. Thus, the score increase to 4 + 2 = 6.
Similarly, each time the score would be increased by 2. Thus, after 11 seconds, the score becomes 24, which is ≥ 23.
Test case 2: The initial score is 9. Lina needs the score to be at least 20.
The smallest prime factor of 9 is 3. Thus, the score increase to 9 + 3 = 12.
The smallest prime factor of 12 is 2. Thus, the score increase to 12 + 2 = 14.
The smallest prime factor of 14 is 2. Thus, the score increase to 14 + 2 = 16.
The smallest prime factor of 16 is 2. Thus, the score increase to 16 + 2 = 18.
The smallest prime factor of 18 is 2. Thus, the score increase to 18 + 2 = 20.
Thus, after 5 seconds, the score becomes 20, which is ≥ 20
2
2 23
9 20
Sample Output
11
5
Explanation
Test case 1: The initial score is 2. Lina needs the score to be at least 23.
The smallest prime factor of 2 is 2. Thus, the score increase to 2 + 2 = 4.
The smallest prime factor of 4 is 2. Thus, the score increase to 4 + 2 = 6.
Similarly, each time the score would be increased by 2. Thus, after 11 seconds, the score becomes 24, which is ≥ 23.
Test case 2: The initial score is 9. Lina needs the score to be at least 20.
The smallest prime factor of 9 is 3. Thus, the score increase to 9 + 3 = 12.
The smallest prime factor of 12 is 2. Thus, the score increase to 12 + 2 = 14.
The smallest prime factor of 14 is 2. Thus, the score increase to 14 + 2 = 16.
The smallest prime factor of 16 is 2. Thus, the score increase to 16 + 2 = 18.
The smallest prime factor of 18 is 2. Thus, the score increase to 18 + 2 = 20.
Thus, after 5 seconds, the score becomes 20, which is ≥ 20