Se consideră şirul Fibonacci, definit astfel: f1=1 , f2=1 , fn=fn-1+fn-2 , dacă n>2.

Cerinţa

Se dau n numere naturale. Să se verifice despre fiecare dacă este termen al şirului lui Fibonacci.

Date de intrare

Programul citește de la tastatură numărul n şi apoi n numere naturale.

Date de ieşire

Programul afișează pe câte o linie a ecranului, pentru fiecare număr, mesajul DA, dacă acel număr este termen al şirului lui Fibonacci, respectiv NU în caz contrar.

Restricţii şi precizări

• 1 ≤ n ≤ 10
• numerele care se verifică au cel mult 9 cifre

Exemplu

Date de intrare

8
13 1 8 24 21 55 47 8

Date de ieșire

DA
DA
DA
NU
DA
DA
NU
DA

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int a[10];
    int f[100];
    f[0]=1 , f[1]=1;
    for(int i = 2 ; i < 45 ; ++i)
    f[i]=f[i-1]+f[i-2];
    for(int i = 0 ; i < n ; ++i)
    cin >> a[i];
    for(int i = 0 ; i < n ; ++i)
    {
        int cnt=0;
        for(int j=0 ; j < 45 ; ++j)
        if(f[j]==a[i])
        cnt++;
        if(cnt==0)
        cout << "NU" << endl;
        else
        cout << "DA" << endl;
    }
    return 0;    
}