#include <iostream>
#include <string>
#include <fstream>

using namespace std;

static const size_t MAXN = 6000000;
static const int MODULES[] = {
	100000007, 100000037, 100000049, 100000073, 100000081, 
	100000123, 100000127, 100000193, 100000213, 100000039};
static const size_t M = 10;

int fibs[M][MAXN];

void init()
{
	for (size_t i = 0; i < M; i++)
	{
		fibs[i][0] = 0;
		fibs[i][1] = 1;
		for (size_t j = 2; j < MAXN; j++)
		{
			fibs[i][j] = fibs[i][j - 1] + fibs[i][j - 2];
			if (fibs[i][j] > MODULES[i])
				fibs[i][j] -= MODULES[i];
		}
	}
}

bool process(string s)
{
	int n[M];
	fill(n, n + M, 0);
	for (size_t i = 0; i < M; i++)
	{
		for (size_t j = 0; j < s.size(); j++)
		{
			n[i] = (n[i] * 10 + s[j] - '0') % MODULES[i];
		}
	}

	size_t size = s.size() * 5 + 10;
	for (size_t i = 0; i < size; i++)
	{
		bool ok = true;
		for (size_t j = 0; j < M; j++)
			ok &= n[j] == fibs[j][i];
		if (ok)
		{
			return true;
		}
	}
	return false;
}

int main()
{
	ifstream in("mushrooms.in");
	ofstream out("mushrooms.out");
	init();
	size_t n;
	in >> n;
	for (size_t i = 0; i < n; i++)
	{
		string s;
		in >> s;
		if (process(s))
			out << "Yes\n";
		else
			out << "No\n";
	}
}
