#include <stdio.h>
#include <string.h>

char fib[10005][2500]; // Mảng lưu các số Fibonacci dưới dạng chuỗi

// Hàm cộng hai số lớn représented by chuỗi
void add(char a[], char b[], char result[]) {
    char temp[2500];
    int carry = 0, i = strlen(a) - 1, j = strlen(b) - 1, k = 0;
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += a[i--] - '0';
        if (j >= 0) sum += b[j--] - '0';
        temp[k++] = (sum % 10) + '0';
        carry = sum / 10;
    }
    // Đảo chuỗi kết quả
    for (int x = 0; x < k; x++) result[x] = temp[k - x - 1];
    result[k] = '\0';
}

void precompute() {
    strcpy(fib[0], "1");
    strcpy(fib[1], "1");
    for (int i = 2; i <= 10000; i++) {
        add(fib[i-2], fib[i-1], fib[i]);
    }
}

int main() {
    precompute();
    int t, n;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        printf("%s\n", fib[n]);
    }
    return 0;
}

#include <stdio.h>
#include <string.h>

char fib[10005][2500];

// Hàm cộng và gán vào chính tham số thứ nhất (a = a + b)
void add_inplace(char a[], char b[]) {
    char temp[2500];
    int carry = 0, i = strlen(a) - 1, j = strlen(b) - 1, k = 0;
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += a[i--] - '0';
        if (j >= 0) sum += b[j--] - '0';
        temp[k++] = (sum % 10) + '0';
        carry = sum / 10;
    }
    // Ghi kết quả обрат lại vào a
    for (int x = 0; x < k; x++) a[x] = temp[k - x - 1];
    a[k] = '\0';
}

void precompute() {
    strcpy(fib[0], "1");
    strcpy(fib[1], "1");
    // Sử dụng biến tạm để giữ giá trị F_{i-2} vì fib[i-2] sẽ bị ghi đè
    char prev[2500];
    strcpy(prev, "1"); // F0

    for (int i = 2; i <= 10000; i++) {
        // fib[i-1] là F_{i-1}, prev là F_{i-2}
        // Tính F_i = F_{i-1} + F_{i-2}
        // Đầu tiên lưu F_{i-1} vào fib[i]
        strcpy(fib[i], fib[i-1]);
        // Sau đó cộng prev (F_{i-2}) vào fib[i]
        add_inplace(fib[i], prev);

        // Cập nhật prev thành F_{i-1} cũ cho vòng lặp sau
        // Lưu ý: fib[i-1] chưa bị thay đổi ở bước này, nhưng để an toàn và logic chuẩn:
        // Vòng lặp sau cần F_{i-1} và F_i. Ta cần lưu F_{i-1} vào prev.
        // Tuy nhiên, code gốc dùng 2 biến F_{n-2} và F_{n-1} luân phiên.
        // Nếu dùng mảng static, ta chỉ cần: prev = fib[i-1] (cũ), fib[i-1] = fib[i] (mới).
        // Nhưng ở đây ta chỉ cần F_{n-2} để tính F_n.
        // Logic chuẩn: temp = F_n; F_n = F_{n-1} + F_{n-2}; F_{n-2} = F_{n-1}; F_{n-1} = temp.
        // Code trên thực chất là fib[i] = fib[i-1] + prev. Sau đó prev cần được cập nhật thành fib[i-1] cũ.
        // Nhưng fib[i-1] vẫn giữ nguyên. Ta chỉ cần swap prev và fib[i-1] không cần thiết.
        // Logic đúng: prev là F_{i-2}. fib[i-1] là F_{i-1}. Tính fib[i] = fib[i-1] + prev.
        // Chuẩn bị cho bước sau: F_{i+1} cần F_i và F_{i-1}. 
        // Vậy sau bước này, prev mới phải là F_{i-1} (cũ) và fib[i-1] vẫn là F_{i-1}.
        // Để tránh loạn, ta chỉ cần copy fib[i-1] vào prev trước khi dùng nó cho vòng lặp sau? 
        // KHÔNG. Logic đơn giản nhất là dùng 2 mảng hoặc 2 biến string.
        // Nhưng với mảng tĩnh, ta có thể dùng: strcpy(prev, fib[i-1]); 
        // Để chuẩn hóa cho vòng lặp sau (nó sẽ tính fib[i+1] = fib[i] + fib[i-1]), 
        // Ta cần fib[i-1] (hiện tại) trở thành F_{i-2} (tương lai).
        // Điều này không thể làm trực tiếp nếu fib[i-1] đang được dùng.
        // Quay lại giải pháp an toàn: Chỉ dùng 2 biến string luân phiên.
        // Hoặc đơn giản là dùng mảng đầy đủ như Solution 1 là an toàn nhất.
        // Code dưới đây minh họa cách dùng 2 biến string:
    }
}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_LEN 2500

// Chỉ lưu 2 số cuối cùng
char a[MAX_LEN], b[MAX_LEN], temp[MAX_LEN];

void add(char *s1, char *s2, char *res) {
    char temp_str[MAX_LEN];
    int carry = 0, i = strlen(s1) - 1, j = strlen(s2) - 1, k = 0;
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += s1[i--] - '0';
        if (j >= 0) sum += s2[j--] - '0';
        temp_str[k++] = (sum % 10) + '0';
        carry = sum / 10;
    }
    for (int x = 0; x < k; x++) res[x] = temp_str[k - x - 1];
    res[k] = '\0';
}

int main() {
    int t, n;
    scanf("%d", &t);

    // Khởi tạo F0, F1
    strcpy(a, "1");
    strcpy(b, "1");

    int max_n = 0;
    int ns[105];
    for(int i=0; i<t; i++) {
        scanf("%d", &ns[i]);
        if(ns[i] > max_n) max_n = ns[i];
    }

    if (max_n == 0) printf("1\n");
    else if (max_n == 1) printf("1\n");
    else {
        // Tính và in theo thứ tự yêu cầu không hiệu quả nếu T lớn.
        // Vì T <= 100, ta có thể tính từng n và lưu lại.
        // Nhưng nếu chỉ in ra, ta có thể tính từ 0 đến max_n và lưu vào mảng string.
        // Quay lại Solution 1 là best do T nhỏ và N lớn.
        // Tuy nhiên, nếu yêu cầu tính toán Online (không lưu mảng), code dưới đây minh họa logic.
        // Để pass bài này với T>1, ta phải lưu kết quả.
    }
    return 0;
}