import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner kb = new Scanner(System.in); StringBuilder sb = new StringBuilder(); int T = kb.nextInt(); int maxN = 1000000; long[] dy = new long[maxN+1]; dy[1] = 1; dy[2] = 2; dy[3] = 4; for(int j=4; j