Given a number K, find the smallest Fibonacci number that shares a common factor( other than 1 ) with it. A number is said to be a common factor of two numbers if it exactly divides both of them. Output two separate numbers, F and D, where F is the smallest fibonacci number and D is the smallest number other than 1 which divides K and F.

/* CODE*/
#include<stdio.h>

long long int common_factor(long long int a, long long int b);
main()
{

int t,a;
long long int temp,fib1,fib2,cf;

    scanf("%d",&t);
    while(t)
    {
        t--;
        scanf("%d",&a);

        fib1 = 1;
        fib2 = 2;   
        while(1)
        {
            cf = common_factor(a,fib2);
            if(cf == 1)
            {
                temp = fib2;
                fib2 = fib1+fib2;
                fib1 = temp;
            }
            else
            {
                printf("%lld %lld\n",fib2,cf);
                break;
            }

        }
    }

return 0;
}

long long int common_factor(long long int a,long long int b)
{
long long int temp;
    while(1)
    {
        if(b==0)
        {
            break;
        }
        else
        {
            temp = a%b;
            a=b;
            b=temp;
        }
    }
   
    return a;
}