Tecnoesis, the techical festival of NIT Silchar is coming and thus Arun,Takle and Handi the core-cordinator of departmental team of CSE, decided to conduct a game. In this game, the participant will be given a whole number N and will be asked questions.

q = the sum of prime divisors of N.
p = the sum of numbers of numbers that are coprime and less than or equal to prime divisors of N .
s= the number of prime divisors of N
Constraints:
1<=T<=10^6
0<=N<=10^6
0<=K<=10^6

As it will be very difficult for Arun,Takle and Handi to tell manually whether the answer given by participant is
correct or not. So, they decided to write a code for it. As Arun is very busy in Tecnoesis preparations and Handi
is busy with his GirlFriend, they have given this task to you.

The first line of the input will consist of a single integer T. The next T lines contains 2 integers N and K, denoting the numbers.

OUTPUT
For each test case output a single integer (one per line) M i.e. (N+K+q-p-s).
Input:
2
24 2
8 2

Output:
26
10

Problem Setter : Avinash Gurjar