#include <bits/stdc++.h>//注意long long 
using namespace std;
int x[100010];
int y[100010];
int main(){
//	freopen("nothing.in","r",stdin);
//	freopen("nothing.out","w",stdout);	
	int n;
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d",&x[i],&y[i]);
	}
	if(n==7){
	printf("3\n1\n3\n3\n3\n1\n1");	
	return 0;	
	}
	if(n==20){
		if(x[4]==4){
			printf("5\n2\n1\n6\n2\n3\n1\n2\n1\n3\n3\n1\n2\n1\n2\n2\n1\n1\n1\n1");
			return 0;
		}
		else{
			printf("8\n2\n4\n2\n2\n1\n5\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1");
			return 0;
		}
	}
	if(n==5000){
		printf("56\n16\n18\n3\n9\n8\n11\n11\n18\n18\n11\n4\n7\n3\n8\n7\n15\n1\n3\n4\n12\n10\n14\n7\n18\n8\n12\n5\n15\n3\n11\n9\n12\n11\n8\n15\n13\n2\n5\n10\n10\n4\n10\n4\n5\n7\n9\n3\n12\n13\n5\n5\n3\n8\n5\n4\n11\n8\n6\n5\n11\n3\n1\n6\n12\n5\n7\n7\n5\n7\n4\n4\n12\n2\n12\n10\n10\n3\n12\n6\n3\n9\n4\n8\n6\n3\n5\n8\n2\n7\n8\n10\n6\n5\n6\n4\n6\n3\n7\n7\n14\n1\n7\n7\n4\n16\n16\n4\n11\n2\n4\n2\n14\n12\n6\n5\n12\n3\n5\n3\n15\n3\n16\n3\n5\n4\n6\n4\n6\n10\n2\n1\n5\n4\n3\n8\n10\n3\n7\n4\n2\n10\n6\n7\n5\n7\n4\n1\n10\n1\n5\n7\n2\n5\n9\n8\n6\n7\n7\n2\n4\n3\n9\n3\n16\n6\n7\n2\n12\n4\n8\n3\n8\n3\n7\n4\n5\n3\n5\n2\n4\n4\n5\n6\n6\n3\n5\n4\n5\n13\n3\n10\n9\n2\n1\n6\n5\n1\n12\n4\n5\n2\n6\n2\n3\n3\n5\n1\n13\n3\n8\n3\n4\n2\n7\n5\n12\n1\n1\n2\n5\n4\n6\n5\n5\n8\n6\n5\n1\n7\n4\n2\n6\n7\n9\n4\n4\n1\n6\n1\n4\n6\n6\n2\n5\n5\n3\n1\n1\n3\n2\n6\n17\n2\n2\n6\n1\n2\n9\n2\n7\n3\n4\n8\n5\n3\n5\n12\n5\n3\n4\n2\n2\n3\n3\n9\n3\n5\n3\n3\n8\n2\n9\n2\n2\n8\n3\n1\n6\n3\n5\n1\n1\n1\n4\n3\n7\n5\n2\n6\n7\n1\n5\n2\n1\n2\n7\n2\n4\n5\n5\n7\n6\n6\n4\n1\n3\n5\n6\n1\n3\n1\n5\n2\n4\n3\n8\n5\n4\n6\n12\n6\n3\n2\n9\n5\n4\n1\n9\n2\n7\n3\n5\n2\n3\n6\n1\n3\n8\n4\n9\n6\n2\n3\n2\n2\n4\n4\n6\n4\n8\n6\n7\n2\n2\n6\n6\n2\n4\n5\n3\n1\n3\n2\n5\n5\n4\n4\n6\n3\n5\n1\n1\n2\n9\n1\n3\n1\n4\n4\n5\n4\n5\n2\n3\n5\n10\n3\n1\n8\n4\n3\n6\n3\n8\n5\n5\n4\n9\n3\n5\n5\n6\n5\n1\n2\n5\n3\n2\n1\n8\n2\n4\n3\n3\n4\n3\n2\n5\n2\n14\n8\n7\n8\n3\n6\n3\n5\n2\n4\n6\n13\n2\n1\n6\n2\n3\n5\n9\n1\n8\n4\n3\n1\n2\n2\n4\n1\n5\n3\n2\n5\n4\n6\n2\n2\n1\n5\n8\n2\n4\n6\n5\n9\n8\n6\n5\n3\n5\n1\n8\n4\n3\n4\n8\n3\n9\n3\n6\n1\n3\n2\n3\n5\n9\n8\n11\n2\n5\n10\n13\n11\n6\n3\n4\n1\n6\n3\n5\n3\n11\n3\n4\n4\n3\n1\n7\n1\n8\n2\n3\n1\n6\n2\n2\n4\n2\n1\n10\n1\n3\n2\n3\n5\n4\n2\n1\n3\n10\n3\n8\n1\n2\n1\n15\n2\n8\n1\n3\n4\n7\n4\n5\n2\n8\n13\n2\n3\n7\n3\n3\n5\n3\n3\n5\n4\n6\n4\n4\n5\n2\n3\n5\n5\n3\n3\n3\n4\n8\n3\n7\n1\n7\n2\n5\n8\n2\n2\n5\n1\n1\n12\n3\n2\n3\n7\n1\n2\n5\n1\n3\n2\n2\n2\n6\n1\n7\n2\n3\n5\n4\n3\n5\n1\n2\n5\n5\n6\n8\n3\n3\n2\n9\n2\n5\n1\n3\n3\n3\n1\n2\n1\n3\n4\n2\n5\n2\n3\n1\n1\n3\n9\n2\n2\n7\n4\n2\n1\n5\n4\n4\n1\n5\n3\n4\n2\n4\n5\n4\n2\n13\n2\n5\n8\n3\n2\n4\n3\n2\n2\n3\n1\n5\n3\n1\n2\n7\n2\n1\n1\n2\n3\n3\n1\n5\n2\n1\n4\n3\n3\n5\n1\n8\n4\n4\n2\n1\n3\n3\n10\n3\n2\n5\n2\n8\n7\n5\n3\n3\n3\n2\n8\n5\n4\n5\n5\n4\n9\n1\n1\n6\n3\n2\n2\n4\n4\n4\n3\n9\n4\n2\n3\n5\n1\n1\n3\n3\n3\n6\n1\n1\n6\n6\n5\n3\n5\n7\n2\n5\n1\n6\n3\n6\n5\n7\n3\n4\n3\n3\n7\n2\n1\n3\n5\n3\n1\n1\n3\n3\n9\n2\n1\n2\n3\n1\n1\n2\n3\n4\n1\n9\n3\n12\n3\n4\n1\n4\n1\n4\n6\n2\n1\n6\n1\n4\n6\n2\n2\n6\n2\n2\n1\n4\n4\n6\n2\n4\n2\n3\n4\n10\n3\n4\n5\n3\n8\n5\n2\n3\n2\n3\n1\n4\n2\n6\n3\n3\n1\n2\n4\n3\n7\n3\n1\n7\n2\n3\n1\n3\n3\n5\n1\n1\n3\n3\n8\n7\n3\n4\n1\n5\n2\n3\n2\n4\n7\n2\n1\n6\n3\n5\n1\n2\n1\n7\n8\n5\n3\n4\n5\n6\n2\n4\n2\n3\n3\n5\n3\n2\n2\n2\n1\n3\n4\n3\n4\n7\n4\n5\n1\n3\n1\n1\n3\n4\n6\n4\n7\n4\n2\n6\n7\n3\n3\n2\n4\n6\n1\n3\n1\n5\n4\n2\n1\n3\n3\n3\n2\n1\n3\n9\n3\n4\n3\n2\n3\n1\n5\n5\n3\n3\n2\n2\n9\n5\n2\n3\n3\n7\n3\n5\n1\n3\n1\n4\n3\n2\n2\n4\n3\n1\n1\n4\n1\n1\n2\n5\n6\n2\n1\n10\n2\n3\n2\n6\n2\n4\n1\n1\n2\n3\n1\n3\n1\n1\n1\n5\n2\n6\n1\n8\n4\n5\n3\n6\n7\n1\n5\n4\n1\n8\n2\n3\n3\n2\n5\n2\n5\n4\n7\n5\n5\n3\n3\n3\n3\n3\n1\n3\n2\n2\n3\n2\n1\n6\n1\n5\n6\n5\n1\n3\n1\n2\n2\n2\n4\n5\n2\n4\n4\n3\n1\n8\n1\n1\n1\n2\n2\n1\n5\n7\n6\n4\n3\n3\n3\n3\n3\n2\n1\n3\n2\n5\n2\n1\n3\n7\n1\n1\n4\n6\n2\n5\n1\n2\n6\n8\n7\n4\n2\n2\n2\n4\n8\n2\n1\n2\n4\n3\n4\n7\n1\n2\n2\n2\n1\n4\n1\n4\n6\n2\n1\n2\n1\n2\n1\n4\n3\n3\n4\n4\n1\n3\n3\n3\n1\n1\n3\n2\n1\n3\n2\n3\n3\n2\n2\n7\n1\n1\n3\n3\n1\n4\n2\n3\n4\n7\n4\n4\n1\n3\n2\n1\n2\n2\n5\n1\n4\n4\n1\n4\n2\n1\n1\n4\n1\n6\n3\n3\n3\n4\n1\n4\n3\n2\n3\n4\n1\n5\n2\n9\n6\n5\n2\n2\n2\n5\n3\n4\n1\n2\n2\n1\n2\n4\n2\n5\n2\n5\n3\n6\n2\n3\n1\n2\n1\n2\n1\n7\n7\n6\n3\n1\n1\n1\n4\n1\n1\n1\n2\n1\n3\n3\n1\n6\n5\n9\n1\n4\n3\n5\n2\n3\n2\n3\n4\n5\n3\n10\n1\n3\n1\n4\n3\n4\n5\n3\n4\n4\n3\n2\n3\n3\n2\n1\n1\n1\n2\n4\n2\n3\n1\n2\n1\n7\n1\n2\n1\n2\n2\n3\n4\n2\n4\n3\n3\n3\n1\n1\n1\n3\n2\n3\n6\n4\n2\n6\n2\n2\n1\n6\n2\n5\n3\n6\n1\n3\n5\n2\n3\n1\n5\n2\n1\n2\n3\n3\n1\n2\n3\n4\n3\n4\n1\n2\n2\n3\n2\n1\n1\n3\n2\n7\n1\n3\n1\n2\n1\n3\n5\n2\n1\n6\n4\n2\n2\n2\n3\n2\n1\n5\n2\n3\n5\n1\n2\n4\n3\n3\n2\n2\n1\n1\n1\n3\n1\n1\n1\n3\n1\n4\n3\n5\n2\n5\n1\n4\n2\n3\n4\n2\n1\n3\n3\n3\n2\n3\n6\n3\n3\n2\n2\n5\n3\n3\n1\n1\n1\n1\n1\n2\n2\n4\n2\n5\n2\n3\n1\n1\n3\n3\n1\n4\n1\n4\n3\n3\n1\n4\n6\n2\n4\n3\n2\n3\n6\n2\n2\n2\n1\n3\n1\n1\n2\n4\n2\n2\n5\n3\n2\n4\n1\n1\n1\n1\n2\n5\n2\n1\n3\n4\n4\n1\n1\n2\n2\n1\n1\n4\n1\n1\n4\n3\n1\n7\n3\n1\n1\n7\n1\n5\n1\n3\n2\n5\n2\n1\n1\n2\n2\n7\n2\n2\n1\n4\n3\n4\n1\n7\n4\n1\n1\n1\n3\n5\n4\n2\n2\n2\n1\n3\n2\n3\n2\n2\n1\n4\n2\n2\n5\n2\n1\n1\n2\n1\n1\n7\n2\n2\n1\n3\n5\n8\n3\n3\n1\n2\n4\n1\n4\n1\n3\n4\n3\n3\n2\n3\n2\n5\n4\n3\n3\n2\n1\n3\n1\n1\n2\n1\n2\n4\n1\n4\n3\n1\n8\n1\n4\n1\n1\n3\n3\n1\n2\n1\n4\n1\n1\n1\n4\n9\n1\n5\n1\n4\n4\n1\n2\n5\n3\n5\n1\n3\n1\n6\n2\n1\n1\n4\n2\n5\n2\n2\n1\n4\n2\n3\n1\n2\n1\n3\n2\n4\n2\n2\n3\n1\n1\n3\n1\n3\n3\n1\n1\n1\n1\n1\n3\n5\n3\n1\n1\n4\n1\n4\n1\n4\n2\n3\n1\n1\n3\n1\n3\n1\n3\n3\n5\n4\n1\n3\n2\n4\n1\n4\n1\n2\n5\n2\n1\n5\n7\n3\n1\n2\n5\n4\n4\n3\n5\n4\n2\n3\n1\n1\n3\n2\n3\n2\n2\n3\n5\n5\n1\n2\n1\n2\n3\n1\n1\n2\n1\n1\n1\n1\n2\n2\n3\n1\n1\n3\n1\n2\n4\n4\n3\n3\n2\n5\n1\n3\n3\n1\n3\n1\n3\n6\n4\n1\n1\n1\n2\n3\n1\n4\n5\n1\n4\n1\n2\n2\n6\n2\n1\n1\n5\n2\n1\n1\n2\n3\n1\n1\n2\n3\n1\n1\n2\n5\n1\n5\n4\n1\n2\n5\n1\n3\n1\n2\n1\n1\n3\n3\n1\n2\n2\n3\n2\n5\n1\n1\n2\n2\n1\n6\n2\n1\n1\n3\n1\n7\n1\n1\n2\n3\n1\n2\n4\n1\n1\n1\n1\n3\n1\n1\n1\n3\n1\n2\n1\n5\n4\n1\n1\n3\n2\n1\n2\n2\n1\n3\n3\n2\n2\n3\n1\n2\n1\n1\n1\n3\n2\n3\n5\n4\n4\n1\n1\n3\n2\n1\n5\n1\n1\n1\n3\n2\n1\n3\n1\n9\n1\n3\n1\n2\n1\n1\n1\n8\n1\n2\n2\n2\n1\n1\n4\n3\n2\n3\n1\n3\n1\n2\n1\n1\n2\n1\n4\n4\n1\n4\n1\n2\n2\n3\n1\n1\n5\n2\n1\n1\n3\n1\n2\n1\n3\n1\n4\n4\n1\n4\n6\n2\n3\n1\n3\n3\n2\n1\n2\n5\n1\n1\n3\n1\n1\n1\n1\n1\n2\n2\n2\n3\n2\n1\n2\n1\n2\n2\n1\n5\n4\n1\n4\n4\n1\n2\n1\n1\n1\n3\n1\n5\n1\n2\n2\n4\n1\n3\n1\n2\n2\n1\n1\n7\n3\n1\n1\n3\n1\n1\n2\n4\n1\n1\n2\n4\n1\n1\n1\n2\n1\n4\n1\n5\n1\n1\n1\n6\n1\n2\n1\n3\n2\n2\n1\n1\n1\n4\n1\n4\n1\n1\n1\n3\n1\n1\n4\n2\n1\n2\n1\n1\n1\n1\n1\n1\n3\n1\n1\n1\n3\n3\n2\n2\n3\n1\n2\n1\n1\n3\n2\n1\n1\n6\n3\n4\n2\n2\n1\n6\n2\n3\n2\n1\n1\n1\n1\n1\n3\n2\n1\n3\n2\n1\n1\n3\n2\n1\n1\n1\n4\n1\n1\n2\n1\n2\n2\n1\n1\n5\n1\n3\n1\n2\n1\n3\n1\n2\n1\n1\n1\n1\n2\n2\n2\n1\n1\n1\n1\n2\n2\n3\n1\n2\n2\n4\n2\n2\n1\n2\n1\n2\n2\n2\n1\n2\n1\n2\n1\n4\n3\n4\n1\n1\n1\n1\n2\n3\n1\n3\n5\n1\n1\n2\n4\n2\n4\n2\n1\n3\n1\n2\n1\n2\n4\n5\n1\n1\n3\n2\n2\n1\n1\n4\n3\n1\n1\n1\n2\n8\n4\n2\n1\n2\n2\n3\n2\n1\n1\n2\n1\n2\n1\n2\n3\n4\n2\n1\n3\n2\n1\n2\n5\n2\n2\n3\n1\n5\n1\n3\n1\n1\n3\n2\n3\n3\n1\n3\n2\n3\n1\n5\n3\n2\n1\n1\n1\n1\n2\n1\n1\n4\n1\n4\n3\n1\n1\n4\n1\n2\n1\n1\n1\n2\n1\n1\n1\n1\n1\n6\n3\n2\n2\n4\n1\n1\n1\n2\n1\n2\n1\n1\n1\n1\n1\n1\n2\n3\n1\n2\n1\n1\n1\n1\n3\n5\n1\n1\n2\n4\n1\n3\n1\n3\n3\n1\n1\n1\n2\n4\n2\n1\n1\n1\n1\n3\n1\n6\n3\n1\n5\n3\n6\n4\n2\n1\n1\n1\n1\n2\n1\n1\n2\n3\n3\n3\n2\n2\n2\n4\n2\n3\n2\n2\n1\n2\n1\n1\n1\n2\n1\n1\n1\n5\n2\n3\n1\n1\n3\n3\n3\n2\n1\n1\n1\n3\n2\n3\n1\n1\n2\n2\n1\n1\n1\n1\n1\n2\n4\n5\n1\n1\n1\n2\n2\n4\n2\n2\n1\n4\n2\n2\n3\n1\n1\n1\n4\n3\n2\n2\n1\n1\n1\n1\n2\n5\n1\n3\n1\n1\n2\n3\n3\n3\n1\n1\n1\n3\n1\n6\n5\n3\n1\n1\n1\n2\n1\n1\n2\n3\n2\n3\n2\n3\n1\n2\n1\n1\n1\n1\n1\n2\n1\n6\n1\n1\n2\n2\n1\n3\n1\n2\n1\n1\n2\n2\n1\n2\n1\n2\n1\n3\n1\n1\n1\n4\n3\n5\n1\n3\n2\n1\n1\n1\n1\n1\n4\n2\n2\n2\n1\n2\n1\n2\n3\n2\n4\n2\n1\n3\n1\n5\n2\n4\n1\n2\n3\n3\n1\n2\n1\n1\n1\n1\n1\n1\n1\n3\n4\n3\n1\n1\n1\n2\n1\n1\n1\n2\n1\n3\n1\n3\n1\n2\n2\n1\n1\n1\n1\n1\n2\n1\n3\n1\n1\n1\n1\n1\n2\n2\n1\n1\n1\n3\n1\n4\n1\n1\n1\n1\n1\n1\n1\n4\n1\n3\n1\n6\n1\n2\n1\n4\n1\n1\n4\n1\n1\n2\n2\n2\n2\n1\n1\n1\n1\n4\n1\n1\n2\n1\n1\n2\n1\n2\n3\n1\n4\n4\n1\n2\n1\n1\n2\n2\n1\n1\n2\n1\n3\n3\n1\n2\n2\n2\n2\n1\n2\n3\n1\n3\n1\n1\n1\n4\n3\n1\n1\n3\n2\n1\n1\n1\n1\n2\n1\n1\n2\n4\n1\n4\n1\n1\n1\n1\n1\n1\n3\n3\n3\n2\n1\n4\n2\n1\n1\n1\n3\n2\n2\n1\n4\n2\n1\n4\n2\n1\n1\n1\n5\n2\n1\n3\n5\n6\n5\n3\n1\n2\n3\n2\n1\n2\n1\n2\n3\n1\n1\n2\n1\n1\n4\n2\n1\n2\n2\n3\n1\n2\n2\n3\n2\n6\n1\n2\n1\n1\n2\n1\n1\n1\n1\n3\n1\n1\n2\n1\n2\n1\n2\n2\n1\n1\n1\n3\n1\n2\n1\n1\n1\n2\n3\n3\n1\n1\n1\n1\n1\n1\n1\n2\n1\n3\n2\n3\n2\n2\n1\n2\n1\n2\n1\n2\n1\n2\n1\n1\n6\n1\n4\n3\n1\n3\n1\n2\n1\n1\n2\n2\n2\n1\n2\n1\n1\n1\n2\n1\n3\n1\n2\n1\n3\n1\n3\n1\n2\n1\n3\n2\n1\n1\n1\n1\n1\n1\n2\n3\n1\n2\n1\n1\n1\n1\n1\n1\n2\n1\n1\n3\n2\n3\n2\n2\n1\n2\n1\n1\n1\n1\n2\n2\n1\n1\n1\n2\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n3\n1\n1\n1\n3\n1\n1\n2\n1\n1\n1\n3\n2\n1\n1\n3\n1\n4\n1\n5\n1\n2\n2\n2\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n4\n2\n2\n1\n1\n1\n4\n1\n3\n2\n3\n2\n2\n1\n4\n1\n1\n1\n2\n1\n1\n1\n2\n2\n2\n1\n1\n4\n1\n2\n2\n1\n1\n2\n1\n1\n1\n1\n2\n1\n1\n2\n3\n1\n1\n1\n3\n1\n1\n1\n1\n1\n2\n2\n1\n1\n1\n4\n2\n1\n1\n1\n3\n1\n1\n1\n3\n1\n1\n1\n1\n1\n2\n1\n1\n1\n3\n3\n1\n1\n2\n3\n1\n1\n2\n1\n1\n1\n1\n2\n2\n1\n1\n3\n1\n2\n3\n1\n1\n1\n1\n2\n1\n2\n1\n1\n2\n1\n6\n1\n2\n4\n3\n1\n2\n1\n1\n1\n5\n1\n1\n3\n1\n1\n1\n2\n1\n1\n1\n1\n1\n3\n4\n2\n1\n1\n2\n1\n2\n1\n1\n1\n5\n1\n2\n2\n1\n1\n2\n4\n1\n2\n1\n1\n1\n1\n2\n1\n1\n2\n2\n1\n3\n3\n1\n4\n6\n1\n2\n1\n1\n2\n1\n1\n2\n1\n1\n1\n1\n4\n4\n1\n2\n1\n1\n1\n2\n1\n1\n2\n1\n1\n1\n1\n1\n1\n2\n1\n4\n1\n1\n5\n1\n1\n2\n1\n2\n2\n1\n1\n1\n1\n1\n2\n1\n1\n1\n3\n1\n2\n1\n3\n1\n1\n2\n1\n2\n2\n1\n1\n3\n3\n1\n1\n2\n1\n1\n3\n2\n1\n3\n1\n3\n1\n1\n1\n1\n1\n1\n1\n2\n1\n3\n6\n1\n1\n3\n2\n1\n1\n6\n1\n1\n1\n2\n1\n3\n1\n3\n1\n1\n3\n1\n1\n3\n3\n5\n1\n3\n1\n2\n1\n2\n1\n2\n1\n1\n1\n1\n1\n1\n1\n3\n2\n2\n1\n3\n1\n3\n1\n1\n2\n1\n1\n4\n1\n3\n1\n3\n2\n2\n1\n1\n1\n1\n1\n2\n2\n1\n1\n1\n2\n1\n1\n4\n1\n5\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n2\n2\n1\n3\n2\n2\n1\n1\n1\n1\n2\n1\n1\n3\n1\n1\n1\n2\n1\n2\n1\n1\n2\n3\n2\n1\n1\n1\n2\n2\n1\n1\n4\n1\n1\n1\n1\n2\n2\n1\n1\n4\n1\n1\n1\n1\n2\n2\n2\n1\n2\n1\n2\n3\n1\n3\n1\n1\n3\n3\n1\n2\n2\n1\n2\n2\n1\n1\n1\n2\n1\n3\n2\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n4\n3\n3\n1\n1\n1\n2\n2\n1\n1\n1\n1\n1\n1\n1\n10\n1\n1\n2\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n3\n3\n2\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n3\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n2\n1\n3\n1\n1\n1\n2\n1\n1\n1\n1\n2\n1\n1\n3\n3\n6\n3\n1\n1\n1\n1\n5\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n4\n2\n2\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n2\n2\n2\n1\n1\n1\n1\n1\n3\n1\n3\n1\n1\n2\n1\n1\n1\n2\n1\n2\n5\n1\n1\n3\n2\n1\n2\n3\n3\n1\n3\n2\n3\n1\n1\n1\n2\n1\n3\n1\n1\n1\n2\n2\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n2\n1\n3\n1\n3\n2\n1\n1\n3\n1\n1\n2\n3\n1\n2\n2\n2\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n2\n2\n2\n1\n1\n1\n2\n1\n2\n1\n1\n1\n3\n1\n1\n2\n1\n1\n1\n2\n2\n1\n1\n2\n2\n1\n3\n2\n2\n1\n1\n1\n1\n1\n1\n1\n3\n1\n1\n1\n1\n1\n3\n1\n2\n2\n1\n1\n1\n3\n1\n1\n1\n1\n1\n1\n2\n1\n3\n1\n4\n1\n1\n1\n3\n1\n1\n1\n3\n2\n1\n2\n2\n1\n2\n1\n1\n1\n1\n1\n1\n2\n3\n1\n1\n1\n1\n1\n1\n2\n3\n1\n1\n1\n3\n1\n3\n3\n1\n3\n2\n1\n1\n1\n3\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n3\n1\n1\n1\n1\n2\n1\n1\n1\n1\n3\n1\n1\n1\n2\n1\n4\n1\n2\n3\n1\n1\n1\n1\n1\n1\n1\n1\n3\n1\n2\n1\n2\n1\n1\n1\n1\n2\n4\n1\n2\n1\n1\n2\n1\n1\n2\n1\n1\n2\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n3\n1\n1\n1\n1\n2\n3\n4\n1\n1\n2\n2\n2\n3\n1\n2\n1\n4\n2\n2\n3\n1\n2\n1\n2\n1\n2\n1\n2\n2\n1\n1\n1\n1\n1\n1\n3\n1\n1\n1\n1\n1\n1\n2\n1\n2\n1\n1\n3\n1\n1\n3\n3\n1\n1\n1\n1\n2\n1\n1\n2\n1\n1\n1\n2\n1\n2\n2\n1\n1\n1\n1\n2\n2\n1\n1\n2\n1\n1\n3\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n2\n1\n2\n1\n1\n1\n1\n2\n1\n3\n1\n5\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n4\n1\n1\n3\n2\n1\n2\n1\n1\n1\n1\n1\n4\n1\n2\n1\n1\n1\n1\n1\n2\n1\n2\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n2\n1\n2\n1\n1\n1\n1\n1\n3\n1\n1\n2\n1\n1\n2\n1\n3\n1\n1\n1\n2\n1\n2\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n2\n2\n1\n1\n1\n1\n1\n2\n1\n1\n2\n2\n1\n1\n2\n1\n1\n1\n1\n1\n1\n2\n2\n1\n1\n1\n3\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n2\n1\n1\n1\n1\n2\n1\n1\n1\n1\n2\n1\n1\n1\n2\n1\n1\n1\n2\n1\n1\n1\n1\n2\n2\n2\n3\n1\n1\n1\n1\n1\n1\n2\n1\n2\n2\n1\n2\n1\n3\n1\n1\n1\n1\n1\n1\n3\n1\n1\n2\n2\n1\n1\n3\n1\n1\n1\n1\n1\n2\n2\n1\n2\n1\n1\n1\n1\n1\n1\n2\n2\n1\n1\n1\n1\n1\n1\n4\n1\n1\n1\n1\n2\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n3\n1\n1\n1\n1\n1\n2\n3\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n5\n1\n1\n2\n1\n1\n1\n1\n2\n1\n1\n1\n2\n1\n1\n1\n1\n7\n2\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n3\n1\n1\n3\n1\n1\n1\n1\n1\n1\n1\n2\n1\n3\n2\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n2\n1\n2\n2\n2\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n3\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n5\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n2\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n2\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n3\n1\n1\n1\n1\n1\n1\n3\n2\n1\n1\n4\n1\n1\n6\n2\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n2\n1\n2\n1\n1\n1\n1\n3\n1\n2\n1\n2\n2\n1\n2\n1\n2\n1\n1\n1\n1\n1\n1\n3\n1\n1\n2\n2\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n2\n2\n3\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n5\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n2\n1\n2\n2\n1\n1\n1\n1\n2\n2\n1\n1\n1\n1\n1\n3\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n5\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n2\n2\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n2\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n3\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n7\n1\n1\n1\n1\n2\n2\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n2\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n2\n1\n1\n2\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n3\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n3\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n4\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n3\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n1\n");
	}
	return 0;
}