#include<cstdio>

 #include<cstring>

 #include<cctype>

 #include<cstdlib>

 #include<cmath>

 #include<iostream>

 #include<sstream>

 #include<iterator>

 #include<algorithm>

 #include<string>

 #include<vector>

 #include<set>

 #include<map>

 #include<deque>

 #include<queue>

 #include<stack>

 #include<list>

 #define fin freopen("in.txt", "r", stdin)

 #define fout freopen("out.txt", "w", stdout)

 #define pr(x) cout << #x << " : " << x << "   "

 #define prln(x) cout << #x << " : " << x << endl

 typedef long long ll;

 typedef unsigned long long llu;

 const int INT_INF = 0x3f3f3f3f;

 const int INT_M_INF = 0x7f7f7f7f;

 const ll LL_INF = 0x3f3f3f3f3f3f3f3f;

 const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f;

 const double pi = acos(-1.0);

 const double EPS = 1e-;

 const int dx[] = {, , -, };

 const int dy[] = {-, , , };

 const ll MOD = 1e9 + ;

 const int MAXN =  + ;

 const int MAXT =  + ;

 using namespace std;

 int pr[MAXN];

 int ps[MAXN];

 void init()

 {

     for(int i = ; i <= ; ++i)

     {

         int tmp1 = i;

         int tmp2 = i;

         for(int j = ; j <= i; ++j)

             if(tmp2 % j == )

             {

                 tmp1 = tmp1 / j * (j - );

                 tmp2 /= j;

                 while(!(tmp2 % j))

                     tmp2 /= j;

             }

         pr[i] = tmp1;

     }

     ps[] = ;

     for(int i = ; i <= ; ++i)

         ps[i] = ps[i - ] + pr[i];

 }

 int main()

 {

     int P;

     scanf("%d", &P);

     init();

     while(P--)

     {

         int x, n;

         scanf("%d%d", &x, &n);

         printf("%d %d\n", x, ps[n]);

     }

     return ;

 }