All submissions for this problem are available.
On Sheldon's birthday bash, he received n number of Magic Gifts in a hotel. Being crazy and very particular about the things, he doesn't want to open them unless they are transferred to his home. Since the Magic Gifts can be very large in number, it is impossible to transfer them to his place manually one by one. Therefore, he seeks your help to perform a Magic-T one or more times to transfer them.
Now, the Magic-T behaves very differently. If n, number of Magic Gifts, is not a prime number, they can be transferred to Sheldon's home using Magic-T at once. Otherwise the gifts will disappear instead of getting transferred. He doesn't want to lose any of his gifts at any cost so he asks you to transfer them using Magic-T as few times as possible.
The first line of input contains an integer T, the number of test cases. Then T test cases follow.
Each test case consists of a line containing a number n, number of Magic Gifts.
Output on a new line the minimum number of times you will have to use Magic-T to transfer n Magic Gifts.
1 <= T <= 10^4
1 <= n <= 10^12
Input: 2 4 5 Output: 1 2
|Time Limit:||0.1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, GO|
Fetching successful submissions
If you are still having problems, see a sample solution here.