/******************************************************************************
* Sample solution for the Numbers problem in NWERC'03
* Author: Andreas Björklund
******************************************************************************/
#include <stdio.h>

#define TABLE_SIZE (327017)
#define SCRAMBLER (1003)

struct tfig
{
  int num;
  int nums[7];
  int mult[7];
};

struct ttab
{
  struct tfig fig;
  int pts[2];
};

struct tfig figs;
struct ttab table[TABLE_SIZE];

int hash(struct tfig* afig)
{
  int i,j,val=0;
  for (i=0;i<afig->num;i++)
    for (j=0;j<afig->mult[i];j++)
      val=(SCRAMBLER*val + afig->nums[i]) % TABLE_SIZE;
  return val;
}

void insertEntry(struct tfig* afig,int *pts)
{
  int val=hash(afig);
  if (!table[val].fig.num)
  {
    int i;
    for (i=0;i<afig->num;i++)
    {
      table[val].fig.nums[i]=afig->nums[i];
      table[val].fig.mult[i]=afig->mult[i];
    }
    table[val].fig.num=afig->num;
    table[val].pts[0]=pts[0];
    table[val].pts[1]=pts[1];
  }
}

int lookupEntry(struct tfig* afig,int *pts)
{
  int val=hash(afig);
  if (afig->num==table[val].fig.num)
  {
    int i=0;
    while (i<afig->num && table[val].fig.nums[i]==afig->nums[i] &&  table[val].fig.mult[i]==afig->mult[i]) i++;
    if (i==afig->num)
    {
      pts[0]=table[val].pts[0];
      pts[1]=table[val].pts[1];
      return 1;  
    }  
  }
  return 0;
}

void insertnum(int tal,struct tfig* fig)
{
  int i=0;
  if (tal)
  {
    while (i<fig->num && fig->nums[i]<tal) i++;
    if (i==fig->num)
    {
      fig->nums[fig->num]=tal;
      fig->mult[fig->num++]=1;  
    }
    else
    {
      if (fig->nums[i]==tal)
      {
        fig->mult[i]++;
      }
      else
      {
        int j;
        for (j=fig->num;j>i;j--)
        {
          fig->nums[j]=fig->nums[j-1];
          fig->mult[j]=fig->mult[j-1];  
        }
        fig->nums[j]=tal;
        fig->mult[j]=1;
        fig->num++;
      }
    }
  }
}

void movenum(struct tfig* org,struct tfig* dst,int cnt)
{
  int i;
  for (i=0;i<org->num;i++)
  {
    dst->nums[i]=org->nums[i];
    dst->mult[i]=org->mult[i];
  }
  dst->num=org->num;
  
  if (org->mult[cnt]>1)
  {
    dst->mult[cnt]--;
  }
  else
  {
    for (i=cnt;i<org->num-1;i++)
    {
      dst->nums[i]=dst->nums[i+1];
      dst->mult[i]=dst->mult[i+1];
    }
    dst->num--;
  }
}

void points(int *tal,int *turn,int *pts)
{
  if (*tal>3)
  {
    int i;
    int isprime=1;
    for (i=2;i*i<=(*tal) && isprime;i++)
    {
      isprime = ((*tal) % i);
    }
    if (isprime)
    {
      pts[*turn]++;
      *turn=1-(*turn);
      (*tal)--;
    }  
  }
  else
  {
    pts[*turn]+=((*tal+1)>>1);
    pts[1-(*turn)]+=((*tal)>>1);
    *turn^= ((*tal) & 1);
    *tal=0;
  }
}

void play(struct tfig* pfig, int *ppts)
{
  int i;
  struct tfig nfig;
  if (lookupEntry(pfig,ppts)) return;
  ppts[0]=ppts[1]=0;
  for (i=0;i<pfig->num;i++)
  {
    int j;
    // Factorize
    for (j=2;j*j<=(pfig->nums[i]);j++)
    {
      int curpts[2]={0,0};
      if (pfig->nums[i] % j == 0)
      {
        int recpts[2];
        int tal1,tal2;
        int turns=1;
        //Divisible, clear all points
        tal1=j;
        tal2 = pfig->nums[i] / j;
        points(&tal1,&turns,curpts);
        points(&tal2,&turns,curpts);
        movenum(pfig,&nfig,i);
        insertnum(tal1,&nfig);
        insertnum(tal2,&nfig);
        play(&nfig,recpts);
        if (recpts[turns]+curpts[0]>ppts[0])
        {
          ppts[0]=recpts[turns]+curpts[0];
          ppts[1]=recpts[1-turns]+curpts[1];
        }
      }
    }
  }
  insertEntry(pfig,ppts);
}

int main(void)
{
  int i,j,n;
  scanf("%d",&n);
  for (i=0;i<TABLE_SIZE;i++)
  {
    table[i].fig.num=0;
  }

  for (i=0;i<n;i++)
  {
    int turn,m;
    int pts[2],pts2[2];
    pts[0]=pts[1]=pts2[0]=pts2[1]=0;
    scanf("%d",&m);
    turn=0;
    points(&m,&turn,pts);
    if (m)
    {
    figs.num=1;
    figs.nums[0]=m;
    figs.mult[0]=1;
    play(&figs,pts2);
    }
    printf("%d %d\n",pts[0]+pts2[turn],pts[1]+pts2[1-turn]);
  }
  return 0;
}