#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

char*mmap();
#define rd_skip() while(*rp++>=48)
#define rd(v) long v=0;{long _c;while(_c=*rp++-48,_c>=0)v=v*10+_c;}

char wbuf[1<<25];

char const mbd[]=
"         \n"
"        2\n"
"        6\n"
"       18\n"
"       54\n"
"      162\n"
"      486\n"
"     1458\n"
"     4374\n"
"    13122\n"
"    39366\n"
"   118098\n"
"   354294\n"
"  1062882\n"
"  3188646\n"
"  9565938\n"
" 28697814\n"
" 86093442\n"
"258280326\n"
"774840978\n"
"328034228\n"
"984102684\n"
"955819346\n"
"870969332\n"
"616419290\n"
"851013517\n"
"556551845\n"
"671411182\n"
" 17744840\n"
" 53234520\n"
"159703560\n"
"479110680\n"
"439087687\n"
"319018708\n"
"957056124\n"
"874679666\n"
"627550292\n"
"884406523\n"
"656730863\n"
"971948236\n"
"919356002\n"
"761579300\n"
"288249194\n"
"864747582\n"
"597754040\n"
"795017767\n"
"388564595\n"
"167449432\n"
"502348296\n"
"508800535\n"
"528157252\n"
"586227403\n"
"760437856\n"
"284824862\n"
"854474586\n"
"566935052\n"
"702560803\n"
"111193703\n"
"333581109\n"
"  2498974\n"
"  7496922\n"
" 22490766\n"
" 67472298\n"
"202416894\n"
"607250682\n"
"823507693\n"
"474034373\n"
"423858766\n"
"273331945\n"
"819995835\n"
"463498799\n"
"392252044\n"
"178511779\n"
"535535337\n"
"608361658\n"
"826840621\n"
"484033157\n"
"453855118\n"
"363321001\n"
" 91718650\n"
"275155950\n"
"825467850\n"
"479914844\n"
"441500179\n"
"326256184\n"
"978768552\n"
"939816950\n"
"822962144\n"
"472397726\n"
"418948825\n"
"258602122\n"
"775806366\n"
"330930392\n"
"992791176\n"
"981884822\n"
"949165760\n"
"851008574\n"
"556537016\n"
"671366695\n"
" 17611379\n"
" 52834137\n"
;

main(){
	char*rp=mmap(0l,1l<<25,1,2,0,0ll);
	char*wp=wbuf;
	rd_skip();
	while(*rp){
		rd(n);
		memcpy(wp,mbd+n*10,10);
		wp+=10;
	}
	write(1,wbuf,wp-wbuf);
	_exit(0);
}