TSHOW2

Luego de investigar como loco Sucesión de Fibonacci  encontre en esta parte algo muy interesante Propiedades de la sucesión

El último dígito de cada número se repite periódicamente cada 60 números. Los dos últimos, cada 300; a partir de ahí, se repiten cada  números.

#include <iostream>
using namespace std;
int main(){
    long long int vec[63];
    long long int vec2[63];
    vec[1]=0;
    vec[2]=1;
    vec[3]=1;
    vec[4]=2;
    vec[5]=3;
    vec[6]=5;
    vec[7]=8;

    vec2[1]=0;
    vec2[2]=1;
    vec2[3]=1;
    vec2[4]=2;
    vec2[5]=3;
    vec2[6]=5;
    vec2[7]=8;
    for(int i=8; i<61; i++)
    {
        vec[i]=vec[i-2]+vec[i-1];
        vec2[i]=vec[i]%10;
    }
    long long int aux=1,aux2=1;
    int n;
    cin>>n;
    while(n--){
        cin>>aux;
        if(aux<7)
        {
            cout<<vec2[aux]<<endl;
        }
        else
        {
            aux2=aux%60;
            if(aux2==0)
                cout<<1<<endl;
            else
                cout<<vec2[aux2]<<endl;
        }
    }
    return 0;
}

Moraleja revisar las propiedades, si hubiera hecho antes eso me hubiera ahorrado mucho tiempo :xD.