Fibonacci

Fui fazer essa bagaça quando rodei meu mouse travou tive que desligar o pc veio vou pedir ajuda aos universitários ae gente…

Dado um número n, sua tarefa é calcula o enésimo elemento da sequência de fibonacci.

Entrada
A primeira linha contém um inteiro t (t<101) que representa o número de casos de teste. Em cada uma das próximas t linhas, existe um número n (n<71).

Saída
Para cada caso de teste, imprima o número de fibonacci mod 9.

Exemplo

Entrada:
2
10
20

Saída:
1
6

alguém se habilita? rsrs

Já tentou usar o Google?