#include <iostream>
#include <stdio.h>
using namespace std;
 
int main() {
	long long n,i;
	int T;
	 clock_t t;
    t = clock();
	scanf("%d",&T);
	while(T-->0)
	{
	scanf("%lld",&n);
	long long first=0,second=1,sum=0; //0 1 1 2 3 5 8...
//	cout<<first<<" "<<second<<" ";
	for(i=0;i<n;i++)
	{
		sum=first+second; //sum=1,2
		first=second;//first=1,1
		second=sum;//second=1,2
	//	printf("%lld ",sum);
	}
//	printf("\n");
	}
	t = clock() - t;
    double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds
    printf("Program took %f seconds to execute \n", time_taken);
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RkaW8uaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBtYWluKCkgewoJbG9uZyBsb25nIG4saTsKCWludCBUOwoJIGNsb2NrX3QgdDsKICAgIHQgPSBjbG9jaygpOwoJc2NhbmYoIiVkIiwmVCk7Cgl3aGlsZShULS0+MCkKCXsKCXNjYW5mKCIlbGxkIiwmbik7Cglsb25nIGxvbmcgZmlyc3Q9MCxzZWNvbmQ9MSxzdW09MDsgLy8wIDEgMSAyIDMgNSA4Li4uCi8vCWNvdXQ8PGZpcnN0PDwiICI8PHNlY29uZDw8IiAiOwoJZm9yKGk9MDtpPG47aSsrKQoJewoJCXN1bT1maXJzdCtzZWNvbmQ7IC8vc3VtPTEsMgoJCWZpcnN0PXNlY29uZDsvL2ZpcnN0PTEsMQoJCXNlY29uZD1zdW07Ly9zZWNvbmQ9MSwyCgkvLwlwcmludGYoIiVsbGQgIixzdW0pOwoJfQovLwlwcmludGYoIlxuIik7Cgl9Cgl0ID0gY2xvY2soKSAtIHQ7CiAgICBkb3VibGUgdGltZV90YWtlbiA9ICgoZG91YmxlKXQpL0NMT0NLU19QRVJfU0VDOyAvLyBpbiBzZWNvbmRzCiAgICBwcmludGYoIlByb2dyYW0gdG9vayAlZiBzZWNvbmRzIHRvIGV4ZWN1dGUgXG4iLCB0aW1lX3Rha2VuKTsKCXJldHVybiAwOwp9

MjAKNTAwMDAwMDAwCjEwMDAwMDAwMDAKMTUwMDAwMDAwMAoyMDAwMDAwMDAwCjI1MDAwMDAwMDAKOTAwMDAwMDAwMAoyMDAwMDAwMDAwCjkxMjQ3OTE3NDIKODkxMjc0MTkyODQ3MQoxMjc0MTQ5MTQ3MTk0MQo1MDAwMDAwMDAKMTAwMDAwMDAwMAoxNTAwMDAwMDAwCjIwMDAwMDAwMDAKMjUwMDAwMDAwMAo5MDAwMDAwMDAwCjIwMDAwMDAwMDAKOTEyNDc5MTc0Mgo4OTEyNzQxOTI4NDcxCjEyNzQxNDkxNDcxOTQx

20
500000000
1000000000
1500000000
2000000000
2500000000
9000000000
2000000000
9124791742
8912741928471
12741491471941
500000000
1000000000
1500000000
2000000000
2500000000
9000000000
2000000000
9124791742
8912741928471
12741491471941