import java.io.*;
import java.math.BigInteger;

public class mushrooms_ak {
    static final int MAXN = 5000000;
    static final int M = 10;
    static final int[] MODULES = new int[M];
    static {
        MODULES[0] = BigInteger.valueOf(100000000).nextProbablePrime().intValue();
        for (int i = 1; i < M; i++) {
            MODULES[i] = BigInteger.valueOf(MODULES[i - 1]).nextProbablePrime().intValue();
        }
    }
    static int[][] fibs = new int[M][MAXN];

    static void init()
    {
	    for (int i = 0; i < M; i++) {
		    fibs[i][0] = 0;
		    fibs[i][1] = 1;
		    for (int 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];
    		}
	    }
    }

    static boolean isFib(String s) {
	    int[] n = new int[M];
	    for (int i = 0; i < M; i++) {
		    for (int j = 0; j < s.length(); j++) {
			    n[i] = (n[i] * 10 + s.charAt(j) - '0') % MODULES[i];
		    }
	    }

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader(new File("mushrooms.in")));
        PrintWriter out = new PrintWriter("mushrooms.out");
        init();
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            out.println(isFib(br.readLine()) ? "Yes" : "No");
        }
        out.close();
    }
}
