Question
Power Pulse
Zara competes in a mage’s trial with an initial strength of P.
Each second, she finds the smallest prime factor of her strength and adds it to her total.
She aims to reach or surpass a target strength of Q.
Find the minimum seconds needed for Zara 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 P and Q, the initial and required score of Zara.
Each test case consists of a single line containing two integers P and Q, the initial and required score of Zara.
Output
For each test case, output the minimum time in seconds, after which Zara's score becomes ≥ Q.
Example
Sample Input
2
2 23
9 20
Sample Output
11
5
Explanation
Test case 1: The initial score is 2. Zara 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. Zara 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. Zara 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. Zara 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.