public static void main (String Args[]){
		
		Scanner sr = new Scanner(System.in); 
		testcases = sr.nextInt();
		while(testcases>0){

			k = sr.nextInt();
			while(k>0){
				
				if(k>10000){
			
			l = l*905611805; 
			k=k-10000;
			}else{
					l = l*2;
					k--;
					
				}
				
			if(l>mod){
			l =  l% mod;
			}
			}
			l--;
			System.out.println(l);
			testcases--;
			l =1;
			
		}
	return;
	}