var pzd=new Array(1,1,2,1,2,1,2,3,1,3,2,1,2,3,3,1,3,2,1,3,2,3,4,2,1,2,1,2,7,2,3,1,5,1,3,3,2,3,3,1,5,1,2,1,6,6,2,1,2,3,1,5,3,3,3,1,3,2,1,5,7,2,1,2,7,3,5,1,2,3,4,3,3,2,3,4,2,4,5,1,5,1,3,2,3,4,2,1,2,6,4,2,4,2,3,6,1,9,3,5,3,3,1,3,5,3,3,1,3,3,2,1,6,5,1,2,3,3,1,6,2,3,4, 5,4,5,4,3,3,2,4,3,2,4,2,7,5,6,1,5,1,2,1,5,7,2,1,2,7,2,1,2,10,2,4,5,4,2,3,3,7,2,3,3,4,3,6,2,3,1,5,1,3,5,1,5,1,3,9,2,1,2,3,3,4,3,3,11,1,5,4,5,3,3,4,6,2,3,3,1,3,6,5,9,1,2,3,1,3,2,1,2,6,1,3,17,3,3,4,9,5,7,2,1,2,3,4,2,1,3,6,5,1,2,1,2,3,6,6,4,6,3,2,3,4,2,4,2,7,2,3,1,2,3,1,3,5,10,3,2,1,12,2,1,5,6,1,5,4,3,3,3,9,3,2,1,6,5,6,4,8,7,3,2,1,2,1,5,6,3,3,9,1,8,1,11,3,4,3,2,1,2,4,3,5,1,5,7,5,3,6,1,2,1,5,6,1,8,1,3,2,1,5,4,9,12,2,3,4,8,1,2,4,8,1,2,4,3,3,2,6,1,11,3,1,3,2,3,7,3,2,1,3,2,3,6,3,3,7,2,3,6,4,3,2,13,9,5,4,2,3,1,3,11,6,1,8,4,2,6,7,5,1,2,4,3,3,2,1,2,3,4,2,1,3,5,1,5,4,2,7,5,6,1,3,2,1,8,7,2,3,4,3,2,9,4,5,3,3,4,5,6,7,2,3,3,1,14,1,5,4,2,7,2,4,6,3,6,2,3,10,5,1,8,13,2,1,6,3,2,6,3,4,2,4,11,1,2,1,6,14,1,3,3,3,2,3,1,6,2,6,1,5,1,8,1,8,3,10,8,4,2,1,2,1,11,4,6,3,5,1,2,3,1,3,5,1,6,5,1,5,7,3,2,3,4,3,3,8,6,1,2,7,3,2,4,5,4,3,3,11,3,1,5,7,2,3,9,1,5,7,2,1,5,7,2,4,9,2,3,1,2,3,1,6,2,10,11,6,1,2,3,3,1,3,11,1,3,8,3,6,1,3,6,8,1,2,3,7,2,1,9,12,5,3,1,5,1,5,1,5,3,1,5,1,5,3,4,15,5,1,5,4,3,5,9,3,6,6,1,9,3,2,3,3,9,1,5,7,3,2,1,2,12,1,6,3,8,4,3,3,9,8,1,2,3,1,3,3,5,3,6,6,9,1,3,2,9,4,12,2,1,2,3,1,6,2,7,15,5,3,6,7,3,5,6,1,2,3,4,3,5,1,2,7,3,3,2,3,1,5,1,8,6,4,9,2,3,6,1,3,3,3,14,3,7,2,4,5,4,6,9,2,1,2,12,6,3,1,8,3,3,7,5,7,2,15,3,3,3,4,3,2,1,6,3,2,1,3,11,3,1,2,9,1,2,6,1,3,2,13,3,3,2,4,5,16,8,1,3,2,1,2,1,5,7,3,2,4,5,3,10,2,1,3,15,2,4,5,3,3,4,3,6,2,3,1,3,2,3,1,5,1,8,3,10,2,6,7,14,3,10,2,9,4,3,2,3,7,3,3,5,1,5,6,4,5,1,5,4,6,5,12,1,2,4,3,2,4,9,5,3,3,1,3,5,6,1,5,3,3,3,4,3,5,3,1,3,3,3,5,4,12,3,11,1,9,2,4,5,15,4,9,2,1,5,3,1,3,2,9,4,6,9,8,3,1,6,3,5,1,5,1,3,5,7,2,12,1,8,1,5,1,5,10,2,1,2,4,8,3,3,1,6,8,4,2,3,15,1,5,1,3,2,3,3,4,3,2,6,3,4,6,2,7,6,5,12,3,6,3,1,11,4,9,5,3,7,2,1,3,5,4,3,2,3,15,7,5,1,6,5,1,8,1,9,12,9,3,8,9,3,1,9,2,3,1,5,4,5,3,3,4,2,3,1,5,1,6,2,3,3,1,6,2,7,9,2,3,10,2,4,3,2,4,2,7,3,2,7,6,2,1,15,2,12,3,3,6,6,7,3,2,1,2,9,3,6,4,3,2);
var pzd2=new Array(6,1,6,15,8,1,3,11,7,3,5,6,3,1,2,4,5,3,3,12,7,3,2,4,6,9,5,1,5,1,2,3,10,3,2,7,2,1,2,7,3,6,12,5,3,4,5,1,15,2,3,1,6,2,7,3,17,6,4,3,5,1,2,10,5,4,8,1,5,7,2,1,6,3,8,3,4,2,4,2,3,4,3,3,6,3,2,3,3,4,9,2,10,2,6,1,5,3,1,5,6,1,2,10,3,15,3,2,4,5,6,3,1,14,1,3,2, 1,8,6,1,3,5,4,12,6,3,9,3,2,7,3,2,6,4,3,6,2,3,6,3,6,1,8,10,2,1,5,9,4,2,7,2,1,3,11,3,7,3,3,5,3,1,5,1,2,1,11,1,2,3,3,6,3,7,5,6,3,4,2,18,7,6,3,2,3,1,6,3,6,8,1,5,4,11,1,6,3,2,3,9,1,6,3,2,6,4,3,6,2,3,6,3,1,6,6,2,7,3,8,3,1,5,4,9,3,17,1,14,1,11,3,1,5,6,1,3,2,4,11,3,1,5,4,2,3,4,2,6,9,6,10,2,3,3,4,2,1,8,6,1,5,4,5,1,2,3,7,6,11,4,14,1,2,10,2,1,2,7,5,6,1,6,8,1,14,4,11,4,2,3,3,7,2,4,6,3,3,2,10,2,9,1,6,3,2,3,7,9,5,4,5,16,3,5,3,3,1,3,8,3,1,6,3,14,1,5,4,8,3,4,3,5,12,10,5,1,5,1,6,2,3,10,2,1,6,9,5,1,5,1,2,10,8,13,2,4,3,2,6,3,4,6,6,3,2,4,11,1,8,7,5,3,6,6,7,3,2,10,2,6,3,1,3,3,8,4,11,1,14,4,3,2,10,2,6,12,10,2,4,5,1,8,1,6,6,17,1,2,3,6,3,3,4,3,2,1,3,12,2,10,5,3,3,7,2,3,3,1,6,3,5,1,5,3,10,2,13,2,1,3,11,1,12,2,3,1,2,3,12,3,4,2,1,17,3,4,8,6,1,5,1,5,3,4,2,4,6,11,3,7,2,13,2,1,6,5,4,2,4,6,2,7,3,8,3,4,2,3,3,4,3,5,6,1,3,3,8,4,3);
pzd3=new Array(3,6,5,1,3,9,2,3,3,3,6,9,4,3,5,4,9,2,7,3,9,5,4,5,6,1,3,6,6,18,2,3,4,2,3,1,2,9,6,3,4,3,3,2,9,1,2,1,12,2,3,3,7,15,3,2,3,6,3,10,2,4,2,4,3,3,2,15,1,5,6,4,5,4,12,3,6,2,7,2,3,1,14,7,8,1,6,3,2,10,5,3,3,3,4,5,6,7,5,7,8,7,5,7,3,8,3,4,3,8,10,5,1,3,2,1,2,6,1,5, 1,3,11,3,1,2,9,4,5,4,11,1,5,9,7,2,1,2,9,1,2,3,4,5,1,15,2,15,1,5,1,9,2,9,3,7,5,1,2,10,18,3,2,3,7,2,10,5,7,11,3,1,15,6,5,9,1,2,7,3,11,9,1,6,3,2,4,2,4,3,5,1,6,9,5,7,8,7,2,3,3,1,3,2,1,14,1,14,3,1,2,3,7,2,6,7,8,7,2,3,4,3,2,3,3,3,4,2,4,2,7,8,4,3,2,6,4,8,1,5,4,2,3,13,3,5,4,2,3,6,7,15,2,7,11,4,6,2,3,4,5,3,7,5,3,1,5,6,6,7,3,3,9,5,3,4,9,2,3,1,3,5,1,5,4,3,3,5,1,9,5,1,6,2,3,4,5,6,7,6,2,4,5,3,3,10,2,7,8,7,5,4,5,6,1,9,3,6,5,6,1,2,1,6,3,2,4,2,22,2,1,2,1,5,6,3,3,7,2,3,3,3,4,3,18,9,2,3,1,6,3,3,3,2,7,11,6,1,9,5,3,13,12,2,1,2,1,2,7,2,3,3,4,8,6,1,21,2,1,2,12,3,3,1,9,2,7,3,14,9,7,3,5,6,1,3,6,15,3,2,3,3,7,2,1,12,2,3,3,13,5,9,3,4,3,3,15,2,6,6,1,8,1,3,2,6,9,1,3,2,13,6,3,6,2,12,12,6,3,1,6,14,4,2,3,6,1,9,3,2,3,3,10,8,1,3,3,9,5,3,1,2,4,3,3,12,8,3,4,5,3,7,11,4,8,3,1,6,2,1,11,4,9,17,1,3,9,2,3,3,4,5,4,9,3,2,1,2,4,8);
pzd=pzd.concat(pzd2).concat(pzd3);
var pz=new Array(2+pzd.length);pz[0]=2;pz[1]=3;
for(var i=0;i<pzd.length;i++)pz[i+2]=pz[i+1]+pzd[i]*2;
pdz=pdz2=pzd3=null;