Fibonacci Factor Problem

Story

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.

Input Format  

First line of the input contains an integer T, the number of testcases.

Then follows T lines, each containing an integer K.

Output Format

Output T lines, each containing the required answer for each corresponding testcase.

Sample Input 

3

3

5

161

Sample Output

3 3

5 5

21 7

Explanation 

There are three testcases. The first test case is 3, the smallest required fibonacci number  3. The second testcase is 5 and the third is 161. For 161 the smallest fibonacci numer sharing a common divisor with it is 21 and the smallest number other than 1 dividing 161 and 7 is 7.

Constraints :

1 <= T <= 5

2 <= K <= 1000,000

The required fibonacci number is guranteed to be less than 10^18.

My Answer: (I am no sure if it is correct.)

#include "stdafx.h"
#include <iostream>

using namespace std;

int fb(int i);

int _tmain(int argc, _TCHAR* argv[])
{
 int count = 0;
 cin >> count;
 int *input = new int[count];
 for (int i = 0; i<count; i++)
 {
  cin >> input[i];
 }

 for (int i = 0; i<count; i++)
 {
  int k = 1;
  int fbNumber = 1;
  while (fbNumber <= input[i]) 
  {
   for (int x=2; x<=fbNumber; x++)
   {
    if (fbNumber % x == 0 && input[i] % x == 0 )
    {
     cout << input[i] << " " << fbNumber << endl;
    }
   }

   k++;
   fbNumber = fb(k);
  };
 }

 return 0;
}

int fb(int i)
{
 if (i<=1)
  return 1;

 if (i==2)
  return fb(1);

 return fb(i-1) + fb(i-2);
}

Reference:
https://amazon.interviewstreet.com/challenges/dashboard/#problem/4fd653336df28