#include <bits/stdc++.h> // https://oeis.org/A077196 太菜了，只会骗分了qwq 
using namespace std;

int a[] = {0,1,1,3,1,1,3,2,1,9,1,2,3,2,2,3,1,2,9,2,1,3,2,2,3,1,2,9,2,2,3,3,1,6,2,2,9,3,2,3,1,5,3,3,2,9,2,2,3,2,1,3,2,3,9,2,2,3,2,2,3,2,3,9,1,2,6,3,2,3,2,3,9,2,3,3,2,2,3,4,1,9,5,3,3,2,3,3,2,2,9,2,2,3,2,2,3,2,2,18,1,2,3,2,2,3,3,3,9,2,2,3,2,2,3,2,2,9,2,3,3,2,2,6,3,1,9,2,1,3,2,2,6,2,3,9,2,2,3,2,2,3,3,2,9,2,2,3,3,2,3,3,2,9,2,3,3,2,4,3,1,2,9,3,5,6,3,2,3,2,2,9,3,3,3,2,2,3,2,2,9,2,2,3,2,3,3,4,2,9,2,3,3,2,2,3,2,2,18,3,1,3,2,3,3,5,2,9,2,2,3,2,3,3,3,3,9,3,2,6,2,3,3,2,2,9,2,3,3,2,2,6,2,2,9,2,2,6,3,7,3,2,2,9,2,2,6,2,3,3,1,2,9,2,2,3,1,2,3,3,2,9,2,2,6,3,2,3,3,2,9,5,2,3,2,2,3,3,2,9,2,2,3,3,3,3,2,5,9,2,2,3,2,2,3,2,3,18,2,2,3,3,3,6,2,2,9,3,2,3,3,3,3,2,2,9,4,3,3,4,1,3,2,3,9,2,3,3,5,2,6,2,3,9,2,3,3,2,2,3,2,4,9,2,3,3,3,3,3,2,2,9,2,2,3,3,2,3,2,3,9,2,2,6,2,2,3,2,2,9,3,3,3,2,4,3,2,3,9,2,2,3,3,2,3,2,2,9,2,2,3,3,2,3,2,4,18,3,3,6,1,2,3,3,2,9,3,6,3,2,5,6,2,2,9,3,2,3,2,2,3,2,2,9,3,2,3,3,3,6,3,3,9,2,3,3,2,2,6,3,2,9,3,3,3,2,2,3,2,2,9,6,2,3,3,2,3,2,2,9,2,2,6,2,2,3,2,3,9,3,2,3,2,4,6,2,3,9,7,3,3,3,2,3,2,2,9,2,2,3,2,2,6,3,2,18,3,3,3,2,1,3,2,2,9,2,2,3,2,2,3,4,1,9,2,2,3,2,3,3,2,2,9,3,2,3,2,3,6,2,3,9,2,5,3,3,3,3,2,2,9,2,5,3,2,2,3,3,2,9,2,3,3,4,3,3,2,2,9,3,2,6,2,3,3,2,3,9,3,2,3,2,2,3,5,2,9,2,2,3,2,3,3,4,2,9,2,3,3,3,2,3,3,2,18,3,2,3,2,3,3,2,3,9,3,2,6,2,2,3,2,2,9,3,3,6,2,2,3,2,3,9,3,3,3,1,2,6,2,3,9,3,4,3,3,2,3,2,4,9,1,2,3,3,2,3,3,2,9,2,2,3,3,2,3,2,5,9,2,2,6,2,2,3,3,2,9,3,2,3,3,4,3,2,2,9,2,2,3,3,2,3,4,3,9,2,2,3,3,3,3,2,3,18,3,2,3,5,2,3,2,2,9,3,2,3,2,4,3,2,3,9,2,3,3,2,2,9,3,3,9,2,2,3,2,2,6,2,2,9,2,3,3,4,2,3,2,4,9,2,3,6,3,2,3,2,2,9,4,3,3,3,2,3,3,3,9,3,2,6,2,2,3,3,3,9,2,2,3,2,2,3,2,3,9,3,2,3,2,5,3,4,3,9,2,2,3,3,2,3,4,3,18,3,3,3,3,3,6,3,1,9,2,4,3,2,3,3,2,2,9,2,3,12,6,3,3,3,2,9,5,2,6,2,2,6,2,3,9,2,3,3,2,3,3,2,2,9,2,3,3,2,2,6,2,2,9,2,3,3,2,3,3,3,3,9,3,2,6,2,3,6,3,2,9,3,2,3,3,4,3,3,2,9,2,2,6,2,3,3,2,2,9,3,3,3,3,2,3,2,2,18,2,2,3,2,2,3,2,3,9,3,6,3,2,2,3,3,3,18,2,3,3,4,2,3,2,2,9,3,2,3,2,3,6,3,2,9,2,2,3,2,2,3,3,4,9,2,3,3,2,2,3,5,2,9,4,3,6,4,2,3,3,2,9,3,7,6,3,4,3,3,3,9,2,2,3,2,2,3,2,2,9,2,2,3,2,2,3,4,2,9,2,2,6,2,3,3,2,3,18,3,3,3,3,3,3,2,2,27,1,2,3,3,2,3,2,3,9,2,2,3,2,3,3,3,2,9,2,2,3,2,4,6,1,5,9,4,2,3,2,3,3,2,2,9,3,3,3,3,2,3,2,3,9,2,3,3,2,2,3,2,2,9,3,2,6,3,2,3,3,2,9,2,2,3,5,4,3,2,3,9,3,3,3,3,2,3,2,3,9,2,2,3,5,3,3,2,2,18,2,2,3,3,3,6,2,2,9,2,2,3,3,2,3,3,4,9,3,2,3,4,2,3,2,2,9,2,3,3,2,2,6,3,2,9,3,2,3,2,2,3,3,2,9,3,3,3,2,3,3,3,2,9,2,2,3,3,5,3,2,3,9,2,2,6,2,3,3,3,2,9,3,3,3,2,4,3,2,2,9,2,2,3,3,2,3,4,3,9,2,2,3,2,3,6,2,3,18,5,3,3,2,2,3,7,2,9,3,4,3,2,2,3,3,2,9,3,3,3,2,3,6,2,2,9,2,2,3,3,2,6,2,2,9,2,3,3,3,2,6,3,2,9,2,2,3,2,2,3,3,4,9,4,3,3,3,3,3,2,1,9,2,2,6,2,2,3,3,2,9,3,3,3,4,2,3,3,3,9,2,5,3,3,2,3,4,2,9,3,1,3,2,3,3,2,3,18,2,2,3,2,3,3,2,3,9,2,2,3,2,2,3,2,3,9,2,3,3,4,2,3,5,4,9,2,2,3,2,3,6,4,2,9,2,3,3,2,3,3,2,2,9,3,3,3,2,3,3,2,3,9,4,4,3,2,2,3,2,3,9,3,2,6,2,5,3,2,3,9,2,2,3,3,4,3,3,2,9,3,2,3,2,2,3,2,3,9,3,2,3,2,2,3,3,3,18,4,3,3,2,3,3,3,5,9,2,2,3,3,2,3,2,3,9,2,3,3,2,2,3,3,2,9,4,3,3,3,2,6,3,3,9,2,2,3,3,3,3,2,2,9,2,2,9,5,3,3,3,3,9,2,2,3,2,2,3,2,2,9,2,2,6,2,2,3,2,3,9,2,2,3,3,2,3,2,4,9,2,3,3,3,2,3,4,2,9,2,2,3,3,2,6,3,3,18,2,2,3,2,2,3,2,3,9,2,4,3,3,2,3,4,3,9,2,3,3,4,3,3,3,3,9,3,3,6,2,6,6,3,2,9,2,3,3,2,3,3,3,2,9,2,2,6,2,3,3,3,2,9,2,3,3,2,2,3,3,3,9,2,3,6,2,2,3,3,2,9,5,3,3,2,4,3,3,2,9,2,2,3,2,2,3,2,3,9,2,3,3,2,4,3,3,2,18,3,3,3,3,3,3,3,3,9,3,4,6,3,3,6,1,2,9,3,2,3,4,2,3,3,2,9,3,3,3,3,2,6,2,2,9,2,2,3,3,2,12,3,6,9,3,3,3,3,3,3,2,3,9,4,5,3,2,3,6,2,2,9,2,3,6,2,2,3,3,2,9,2,2,6,3,4,3,2,2,9,3,3,3,2,2,3,2,7,9,3,2,3,3,4,3,5,2,18,2,2,6,2,2,3,2,3,9,3,2,3,3,2,3,2,2,9,3,2,3,4,3,3,3,2,9,3,3,3,2,2,6,4,2,9,3,2,6,3,3,3,2,2,9,2,3,3,2,2,3,3,3,9,4,3,3,2,3,3,2,2,9,3,2,6,2,3,6,2,2,9,3,2,3,3,2,3,2,5,9,2,3,3,3,2,3,2,3,9,2,3,3,2,2,3,2,4,18,2,2,3,2,3,3,2,2,9,2,4,3,3,2,3,3,3,9,2,3,3,6,2,3,2,2,9,2,2,3,3,3,6,3,4,18,3,2,3,3,2,3,2,4,9,2,3,3,3,2,3,2,2,9,2,3,3,2,2,3,3,2,9,3,2,6,3,3,3,2,3,9,3,2,3,2,2,3,2,2,9,2,2,3,3,3,3,4,3,9,2,2,3,3,2,3,3,2,18,2,3,3,3,5,3,2,2,9,3,4,3,3,2,6,5,4,9,2,2,3,4,3,3,2,3,9,3,3,3,7,2,6,2,3,9,4,4,3,2,3,6,3,2,9,5,2,3,2,2,3,3,2,9,2,3,3,3,2,3,2,3,9,2,2,6,2,2,3,3,2,9,2,3,3,2,4,3,2,3,9,3,2,3,2,4,6,2,2,9,3,2,3,4,2,3,3,2,18,3,3,3,3,3,3,3,3,9,3,4,3,2,2,6,2,2,27,3,1,3,2,3,3,2,3,9,2,5,3,2,2,6,3,3,9,2,2,3,2,3,3,3,2,9,3,3,3,2,3,3,2,3,9,6,2,3,2,3,3,2,2,9,4,2,6,4,1,3,5,2,9,2,4,6,2,4,3,3,2,9,3,2,3,2,2,3,2,2,9,3,3,3,3,3,3,3,3,18,2,2,3,3,2,3,3,2,9,2,2,6,3,2,3,2,2,9,2,2,3,4,2,3,2,2,9,3,3,3,2,3,6,2,3,9,2,4,3,3,3,6,2,4,9,2,2,3,2,2,3,2,5,9,4,3,3,2,2,3,3,2,9,2,3,6,3,3,3,3,3,9,2,2,3,3,2,3,3,3,9,2,2,3,2,2,3,2,5,9,3,2,3,5,2,3,2,3,18,2,2,3,2,3,3,2,3,9,3,4,6,3,2,3,2,3,9,2,2,6,2,3,3,3,3,9,2,2,3,2,3,6,4,3,9,3,3,3,2,3,3,2,4,9,2,2,3,3,2,3,2,3,9,4,2,3,3,2,3,3,2,9,2,3,6,2,3,3,2,3,9,2,3,3,2,6,3,3,2,9,2,4,3,4,3,3,2,3,9,2,3,3,3,2,3,2,2,18,3,3,3,2,3,3,2,2,9,2,2,3,2,4,3,2,3,9,5,2,3,2,2,3,3,2,9,2,2,3,2,2,6,3,2,9,3,2,3,2,3,3,2,2,9,4,3,3,3,2,3,4,2,9,4,3,3,3,2,6,2,2,9,2,2,6,2,3,3,3,3,9,2,3,3,3,4,3,3,2,9,3,2,3,2,3,3,4,2,9,3,2,6,2,2,3,3,2,18,2,5,3,3,2,3,2,2,9,2,4,3,2,7,3,2,2,9,3,3,3,4,3,3,2,2,9,2,3,3,3,3,12,2,2,9,2,3,3,3,2,3,5,2,9,3,2,6,2,2,3,2,3,9,4,2,3,2,2,3,2,3,18,2,3,6,3,2,3,2,2,9,4,2,3,3,2,3,2,3,9,2,2,6,3,3,3,2,3,9,3,2,3,2,3,3,2,2,18,2,3,3,3,3,3,4,3,9,3,4,3,3,2,3,3,3,9,3,2,3,4,2,3,1,5,9,2,2,3,2,3,6,3,2,9,2,3,3,2,3,3,2,4,9,2,3,3,3,2,3,2,4,9,2,2,3,3,3,3,3,3,9,2,2,6,5,2,3,2,3,9,2,2,3,3,4,3,2,4,9,3,3,3,1,2,3,4,2,9,3,3,3,2,2,3,3,3,18,2,2,6,2,2,3,2,2,9,3,2,3,3,2,3,3,3,9,2,2,3,2,3,3,3,2,9,2,4,3,2,2,6,3,2,9,2,2,3,3,3,3,2,4,9,2,2,3,3,5,3,4,3,9,8,2,3,2,2,3,3,2,9,3,3,6,2,4,3,2,2,9,2,2,3,3,2,3,2,2,9,3,2,3,2,2,3,2,2,9,5,3,3,3,3,3,3,2,18,3,3,3,3,2,3,3,2,9,3,4,3,4,2,3,2,2,9,2,2,3,2,2,3,3,2,9,6,3,3,2,2,6,3,2,9,5,3,3,2,2,3,3,2,9,3,2,3,2,3,3,2,3,18,4,2,3,2,3,3,2,3,9,3,3,6,2,2,3,2,2,9,2,5,3,2,2,3,3,2,9,3,3,3,2,3,3,2,2,9,2,4,3,2,3,3,3,3,18,2,4,3,3,2,3,3,2,9,3,2,3,2,3,3,5,2,9,5,2,6,2,3,3,3,3,9,2,2,3,3,2,6,3,3,9,3,2,3,3,3,3,3,2,9,2,2,3,3,3,3,2,2,9,4,4,6,3,3,3,2,3,9,2,3,6,3,3,3,3,3,9,2,2,6,2,6,3,2,3,9,3,2,3,2,2,3,2,2,9,3,2,3,2,3,9,3,5,18,3,3,3,2,3,6,3,3,9,3,2,3,2,2,3,2,2,9,2,2,3,2,2,3,2,2,9,2,2,3,2,2,6,3,2,9,2,2,3,5,2,3,3,4,9,2,2,3,2,2,3,6,3,9,2,2,3,2,2,3,4,2,9,3,2,6,3,2,3,3,3,9,2,3,3,3,4,3,2,3,9,2,2,3,2,2,3,4,3,9,2,3,6,2,3,3,3,3,18,2,2,3,2,3,3,3,2,9,2,10,3,2,2,3,3,3,9,3,2,3,4,5,3,3,3,27,2,3,3,2,4,6,3,2,9,3,2,3,3,2,3,2,4,9,3,3,3,2,3,3,3,2,9,2,3,3,3,3,6,3,2,9,6,2,6,3,3,3,2,2,9,3,2,3,3,4,3,2,2,9,3,4,3,2,3,3,2,2,9,2,2,3,2,3,6,3,2,18,3,3,3,3,3,6,2,3,9,3,2,6,3,3,3,2,2,9,2,2,3,4,3,3,3,2,9,3,2,3,3,3,6,3,2,9,2,7,3,2,3,3,2,4,9,3,5,3,3,3,3,2,2,9,4,1,3,3,3,3,2,4,9,2,2,6,2,2,3,4,2,9,2,3,3,3,2,3,3,3,9,4,2,3,3,3,3,6,2,9,4,2,3,3,3,3,2,2,18,2,3,3,3,2,3,2,3,9,3,4,3,2,3,3,3,2,9,3,3,3,4,5,6,3,3,9,3,2,6,3,1,6,2,3,9,2,3,3,2,2,3,2,4,9,2,3,3,2,3,3,2,2,9,2,3,3,3,3,3,2,3,9,2,3,6,2,2,3,2,5,9,2,2,3,2,2,3,3,3,9,2,2,12,2,3,3,6,2,9,2,3,3,3,2,3,2,3,18,3,3,3,3,2,3,3,2,9,4,4,3,5,3,3,3,2,9,3,3,6,2,2,3,2,3,9,2,2,3,3,2,6,2,2,9,2,2,3,3,3,3,2,4,9,2,2,3,2,3,6,3,3,9,4,3,3,2,2,3,2,2,9,2,3,12,3,3,3,3,2,9,2,3,3,2,2,3,7,3,9,3,3,3,2,3,3,4,3,9,4,3,3,2,5,3,2,2,18,3,2,3,2,2,6,3,2,9,2,4,3,3,2,3,3,3,9,2,3,3,2,2,3,3,3,9,2,3,3,4,2,6,2,2,9,5,3,3,2,2,3,2,4,9,3,2,3,3,3,3,2,2,9,4,3,3,3,2,3,3,2,9,2,4,6,2,4,3,2,2,9,3,3,3,2,4,6,3,3,9,3,3,3,3,2,3,2,2,9,2,2,3,3,2,3,2,2,18,2,3,3,2,3,3,3,3,9,2,4,3,3,3,3,2,2,9,3,5,3,4,2,3,2,2,9,2,3,3,2,3,6,2,2,9,3,3,6,2,2,3,2,4,9,3,3,3,2,3,3,3,3,9,2,2,3,5,2,3,5,2,9,2,2,6,3,2,3,4,3,9,2,2,3,2,2,3,3,2,9,3,2,3,3,3,3,4,2,9,2,2,3,3,2,3,4,3,18,3,2,6,2,3,3,2,2,9,3,2,3,4,2,3,2,2,9,2,2,9,4,3,3,3,3,9,2,2,3,3,3,6,3,3,9,3,2,3,3,2,3,2,6,9,2,2,3,2,2,3,2,2,9,2,2,3,2,2,3,2,3,9,3,3,6,3,3,3,4,2,18,3,3,3,2,2,3,3,3,9,2,3,3,5,2,3,4,4,9,3,2,3,3,2,3,3,3,18,2,4,3,3,2,3,2,3,9,2,2,3,3,2,3,3,2,9,2,4,3,4,3,3,2,3,9,2,3,3,2,2,6,2,3,9,3,2,3,2,2,6,3,4,9,2,3,3,2,4,3,2,2,9,2,3,3,2,2,6,2,2,9,2,2,6,2,5,3,3,3,9,3,6,3,2,4,3,3,2,9,3,2,3,2,3,3,4,3,9,2,3,3,3,3,3,2,2,18,3,2,3,3,2,3,2,3,9,5,2,3,3,2,3,2,2,9,3,3,3,4,3,3,3,3,9,2,3,6,2,5,6,4,3,9,3,2,3,2,3,3,2,4,9,3,2,3,3,2,6,3,3,9,4,3,3,3,2,3,2,7,9,2,3,6,3,2,3,3,2,9,2,4,3,4,4,3,2,2,9,3,2,6,2,3,3,2,2,9,3,5,3,2,4,3,3,2,18,2,2,3,3,3,3,2,4,9,4,2,3,3,3,3,3,3,9,2,2,3,4,2,3,3,2,9,2,2,3,2,3,6,5,2,9,2,2,3,3,3,3,2,4,9,3,2,3,3,3,3,3,2,9,4,2,3,3,2,3,3,3,9,2,3,6,2,3,3,2,2,9,4,3,6,3,2,6,2,3,9,2,3,3,2,3,3,4,4,9,2,3,3,3,3,3,2,3,18,3,3,6,3,3,3,2,3,9,3,2,3,4,3,3,3,5,9,3,3,3,4,3,3,3,2,9,2,2,6,3,2,6,2,3,27,2,3,3,1,2,3,3,2,9,3,2,3,2,2,3,3,2,9,4,2,3,5,2,3,2,2,9,2,2,6,3,3,6,3,3,9,3,2,3,2,2,3,3,2,9,3,3,3,2,3,3,2,2,9,2,3,3,3,2,3,2,2,18,3,3,3,7,2,12,3,3,9,3,6,3,2,2,3,3,2,9,3,3,3,4,2,3,2,3,9,3,4,3,2,2,6,2,4,9,1,3,3,2,5,3,2,2,9,2,2,3,4,3,6,3,2,9,4,2,3,2,3,3,2,3,9,4,3,6,2,2,3,2,2,9,2,3,3,3,2,3,2,2,9,6,3,3,3,2,3,4,3,9,3,3,3,2,3,3,3,2,18,3,2,6,2,3,3,3,3,9,2,2,3,3,3,3,2,2,9,2,2,3,2,3,6,3,3,9,2,6,3,3,2,6,2,3,9,3,2,3,2,4,3,3,4,9,2,2,3,3,2,3,2,2,9,2,3,6,3,2,3,2,2,9,3,5,6,2,2,6,3,2,9,3,2,3,4,2,3,2,3,9,3,2,6,3,2,3,4,4,9,2,2,3,2,3,3,3,2,18,2,2,3,2,2,3,5,3,9,3,4,3,3,3,3,2,2,9,2,2,3,4,3,3,2,3,9,2,2,3,3,2,6,3,3,9,3,2,3,2,3,3,3,4,9,2,2,6,2,4,3,3,3,9,2,3,3,2,3,3,3,3,9,2,2,6,2,3,3,2,2,9,2,3,3,2,2,3,5,2,9,2,3,3,2,4,3,4,5,9,2,2,3,3,2,3,3,3,18,2,2,3,2,3,3,3,2,9,3,4,3,3,2,3,3,3,9,2,3,3,4,3,6,3,3,9,2,2,3,5,2,6,3,3,9,3,2,3,2,2,6,3,2,9,3,3,3,2,3,3,3,3,9,4,2,3,2,3,3,3,2,9,3,2,6,2,4,3,3,3,9,3,3,3,3,4,3,2,2,9,3,3,3,2,2,3,4,2,9,2,2,3,2,2,3,4,3,18,2,2,3,2,2,3,3,2,9,2,4,3,2,5,3,3,3,9,2,2,3,6,3,3,2,2,9,3,2,3,3,4,6,3,2,9,3,3,3,3,2,3,3,4,9,3,2,6,3,3,3,3,2,9,6,3,3,2,3,3,2,2,9,3,2,12,4,3,3,2,4,9,3,2,3,2,2,3,3,3,9,3,2,3,3,7,3,2,3,18,2,3,3,2,2,6,2,3,18,3,3,3,3,3,3,2,2,9,3,4,3,2,2,3,2,2,9,3,2,3,2,3,3,2,2,9,4,2,3,2,2,6,3,4,9,3,5,3,2,3,3,2,2,9,2,3,3,3,3,3,2,5,9,2,2,3,2,2,3,3,2,9,2,3,6,2,3,3,2,3,9,3,3,3,2,4,3,5,2,9,3,4,3,3,2,3,2,3,9,2,4,3,3,7,3,2,3,18,2,2,3,2,4,3,2,4,9,2,4,3,3,3,3,3,3,9,2,2,6,4,2,3,2,3,9,3,2,3,2,2,6,3,2,9,3,2,3,2,3,3,3,4,9,3,2,3,3,2,3,2,3,9,4,3,3,3,3,3,2,5,9,3,3,6,2,2,3,3,2,9,3,3,3,2,4,3,2,3,9,3,3,3,2,2,6,4,2,9,2,4,3,4,3,3,2,3,18,3,2,3,5,3,3,3,3,9,2,4,3,2,2,3,2,2,9,2,2,3,4,3,3,4,2,9,7,3,3,2,2,6,2,3,9,2,3,3,3,2,3,4,4,9,3,3,3,2,2,3,2,3,9,2,2,3,3,3,3,2,3,9,3,2,12,4,2,3,2,3,9,2,2,3,3,4,3,3,3,9,2,2,3,2,5,3,2,2,9,3,3,3,2,3,6,2,2,18,2,2,3,2,2,3,3,3,9,2,4,3,2,2,3,3,2,9,2,3,3,4,2,3,3,3,18,5,2,3,3,3,6,2,3,9,2,2,3,4,2,3,2,4,9,3,4,3,2,3,3,2,3,9,2,3,3,2,2,3,3,2,9,2,2,6,2,3,6,6,3,9,3,2,3,2,2,3,3,2,9,2,3,3,2,2,3,4,2,9,3,2,3,3,2,3,2,4,18,3,2,3,3,3,3,3,3,9,3,6,3,3,4,3,3,2,9,2,3,3,4,2,3,3,3,9,2,2,3,3,3,6,3,2,9,3,3,3,2,3,3,2,4,27,2,2,3,3,1,3,5,3,9,2,2,3,2,2,3,2,2,9,3,3,6,3,3,9,2,2,9,2,2,3,3,4,3,3,2,9,3,3,3,3,2,6,4,3,9,3,2,6,3,2,3,2,3,18,2,2,3,3,2,3,4,3,9,2,2,3,2,3,3,3,3,9,3,6,3,4,3,3,3,3,9,2,2,3,2,2,6,3,5,9,2,2,3,2,2,3,3,2,9,2,2,3,2,2,3,2,3,9,4,2,3,3,2,3,4,3,9,2,3,6,3,3,3,3,1,9,2,3,3,5,4,3,2,2,9,4,3,3,3,4,3,4,2,9,2,3,3,3,3,3,3,3,18,5,2,6,2,2,6,3,2,9,2,4,3,3,2,3,2,2,9,2,3,3,2,2,3,2,3,9,2,3,3,2,3,6,3,4,9,3,2,6,2,2,3,3,2,9,3,3,3,3,3,3,2,2,9,4,2,3,4,5,3,2,2,9,2,3,6,3,3,3,2,3,9,3,2,3,2,2,3,3,3,9,3,3,3,2,2,3,4,4,9,3,2,3,2,3,3,2,3,18,5,2,3,3,4,3,3,2,9,3,8,3,2,2,3,3,2,9,2,3,3,4,3,3,2,2,9,2,3,3,3,3,6,2,2,9,4,3,3,3,2,6,2,6,9,4,2,3,2,2,3,4,3,9,2,2,3,2,2,3,2,2,9,3,3,6,2,2,3,3,2,9,2,3,3,3,2,3,2,3,9,2,5,3,3,3,3,4,3,9,3,4,3,3,3,6,2,2,18,3,3,3,3,3,3,4,3,9,2,2,3,3,3,3,2,3,9,3,3,3,4,2,3,5,4,9,2,3,3,3,2,6,2,2,9,3,2,3,2,3,3,3,2,9,2,2,3,3,3,3,2,3,9,2,6,3,3,2,3,2,2,9,2,3,6,2,3,3,2,2,9,2,5,6,3,4,3,3,2,9,2,2,3,3,3,3,2,2,9,3,3,3,2,2,3,3,2,18,3,2,3,2,2,6,3,5,18,2,4,3,2,3,3,3,2,9,3,3,3,4,2,3,3,3,9,3,3,6,3,3,6,3,2,9,2,3,3,2,2,3,2,2,9,3,2,3,5,2,3,7,2,9,2,2,3,2,3,3,2,3,9,3,3,6,3,3,3,2,2,9,3,3,3,3,2,3,2,3,9,2,2,3,4,2,3,2,2,9,3,3,3,3,3,3,3,2,18,2,2,3,4,3,3,3,3,9,2,4,3,2,3,3,2,3,9,3,3,3,2,2,3,2,2,9,3,2,3,2,5,6,2,3,9,2,5,3,2,2,6,3,2,9,3,3,3,3,3,3,3,3,9,4,2,3,2,3,3,2,3,9,2,4,6,3,3,3,3,3,9,6,3,3,2,4,3,2,3,9,3,3,3,3,3,3,2,3,9,2,2,3,2,3,3,2,3,18,3,2,3,2,2,3,2,2,9,2,4,3,4,2,6,2,3,9,3,2,3,2,2,3,3,2,9,3,2,3,3,3,6,2,3,9,3,2,3,3,3,3,3,2,9,2,2,12,2,3,6,3,2,9,6,5,3,2,2,3,3,3,9,3,3,6,2,3,3,3,2,9,2,3,3,4,2,3,2,3,9,2,3,3,2,2,3,4,2,9,3,3,9,2,3,3,5,2,18,2,3,3,3,3,3,2,2,9,3,4,6,3,3,6,3,3,9,2,3,6,2,2,3,4,2,9,2,3,3,2,2,6,2,3,9,2,2,6,2,2,3,3,2,9,2,3,3,3,2,3,2,3,9,4,2,3,2,2,3,3,2,9,2,2,6,3,3,3,2,2,9,3,2,3,2,2,3,2,5,9,2,2,3,3,3,3,4,3,9,3,2,3,2,4,3,3,2,18,2,3,3,2,6,3,3,2,9,2,2,3,2,2,3,2,2,9,2,2,3,6,4,3,2,3,9,2,3,3,2,3,6,2,3,9,2,3,3,2,3,3,3,4,9,3,2,3,3,4,3,3,3,9,4,2,3,3,2,6,3,2,9,2,2,6,2,3,3,3,2,9,2,2,3,3,4,3,3,3,9,3,2,6,3,2,6,2,2,9,3,3,3,3,3,3,3,2,18,3,2,3,2,5,3,3,2,9,3,4,3,2,3,3,2,3,9,4,2,3,10,4,3,2,2,9,2,2,3,3,3,6,3,7,9,3,3,3,2,2,3,3,4,9,5,3,3,3,3,3,3,3,27,4,2,3,3,3,3,4,2,9,4,2,6,2,3,3,2,2,9,2,3,3,2,4,3,2,3,9,2,3,3,2,2,6,4,2,9,3,3,3,3,3,3,2,2,18,3,2,3,3,3,3,2,2,9,2,2,3,3,2,3,3,3,9,3,4,6,4,3,3,2,2,9,3,6,3,2,3,6,2,3,9,3,2,3,3,2,3,2,4,9,2,3,3,2,3,3,2,3,9,4,3,3,3,2,3,2,2,9,3,3,6,4,3,3,5,2,9,3,2,3,2,2,3,2,3,9,2,2,3,2,2,3,2,2,9,3,2,6,3,3,3,2,3,18,2,3,6,3,2,3,2,3,9,3,4,6,3,2,3,3,3,9,2,3,3,2,2,6,4,3,9,3,3,3,3,2,6,2,2,9,2,2,3,2,3,3,3,4,9,3,2,3,3,3,3,2,5,9,4,3,3,2,2,3,3,3,9,3,3,6,4,3,3,2,2,9,2,2,3,7,4,3,2,2,9,3,2,3,2,2,3,4,3,9,2,3,3,5,5,3,3,3,18,3,3,3,4,2,3,2,2,9,2,4,3,1,2,3,3,3,9,3,2,3,4,2,3,4,2,9,2,2,3,2,2,6,3,2,9,2,2,3,3,4,3,2,2,9,3,2,3,3,2,3,2,3,9,2,3,3,2,3,3,3,2,9,2,4,6,2,3,3,3,3,9,3,3,3,3,6,3,2,2,9,3,4,3,2,3,3,2,3,9,3,2,3,2,2,3,2,3,18,2,2,3,3,3,3,2,3,9,2,4,3,3,2,6,3,2,9,5,3,3,4,3,3,2,2,18,3,3,3,2,3,6,2,3,9,2,3,3,3,3,3,2,4,9,5,2,6,2,3,3,3,2,9,4,3,3,2,3,6,2,3,9,1,3,6,3,2,3,3,3,9,3,2,3,3,4,3,3,2,9,2,2,3,2,2,3,4,2,9,3,2,3,3,3,3,3,2,18,3,5,3,4,2,3,2,3,9,2,2,3,3,2,3,2,3,9,3,2,3,4,2,3,3,3,9,4,2,3,3,3,6,2,2,9,2,2,3,3,2,3,5,4,9,2,2,3,2,2,3,2,2,9,2,2,3,3,3,3,3,4,9,3,2,6,2,3,12,2,2,9,3,3,3,3,6,3,2,2,9,2,2,6,3,3,3,4,3,9,2,3,3,2,2,3,3,2,18,3,3,3,3,2,3,3,3,9,2,4,3,3,3,3,2,3,9,2,4,3,4,4,3,3,5,9,3,3,3,4,3,6,2,2,9,2,3,3,3,2,6,2,2,9,2,2,3,3,2,3,3,3,9,4,2,3,2,3,3,3,3,9,2,3,6,5,2,3,2,4,9,2,2,3,2,4,3,3,3,9,3,3,3,2,2,3,4,3,9,3,2,3,2,3,3,3,2,18,3,2,6,2,3,3,3,2,9,4,4,3,3,3,3,2,2,9,2,2,3,2,2,3,2,2,9,2,2,3,3,3,12,3,3,9,3,3,3,2,3,3,2,2,9,3,2,3,3,5,3,3,2,9,2,2,3,2,7,3,3,2,9,3,3,6,3,2,3,2,2,9,3,3,3,2,4,3,3,4,9,4,4,3,3,3,3,2,2,9,5,2,3,3,2,3,2,3,18,2,3,3,2,2,3,2,2,9,2,4,6,3,3,3,2,3,9,3,2,3,4,3,3,3,3,9,2,2,3,3,3,6,3,4,9,2,2,3,3,3,3,5,2,9,2,2,3,2,3,6,3,2,9,4,2,6,3,3,3,2,4,9,2,2,6,3,2,3,2,3,9,2,5,3,3,2,3,2,2,9,2,3,3,3,2,3,4,3,9,2,3,3,2,3,3,2,3,18,3,2,3,2,2,3,2,3,9,3,4,3,3,3,3,5,3,9,2,3,3,4,3,3,2,2,9,2,2,3,4,2,6,2,2,9,4,2,3,3,2,6,2,2,9,2,3,3,3,2,3,3,2,9,4,3,6,3,3,3,3,3,9,2,3,6,3,2,3,3,3,9,2,2,3,3,2,3,2,3,9,3,2,3,2,2,3,6,3,9,2,3,3,3,2,3,2,5,18,7,2,3,3,4,3,3,2,9,3,4,3,3,3,3,3,3,9,2,2,3,4,3,3,3,3,9,3,3,3,2,2,6,2,3,9,2,3,6,5,2,3,2,4,9,2,2,3,2,2,3,2,2,9,2,2,6,3,3,3,3,2,27,3,3,6,3,2,3,2,2,9,3,3,3,3,2,6,3,2,9,2,2,3,3,2,3,4,2,9,3,3,3,3,2,3,3,2,18,3,4,3,3,3,3,3,3,9,3,2,3,2,3,3,2,5,9,2,4,3,4,5,3,2,3,9,2,2,3,2,3,6,3,3,9,2,3,3,2,4,3,3,4,9,3,2,3,2,3,3,4,2,9,2,3,3,2,3,3,2,3,9,5,3,6,2,3,3,3,3,9,3,2,3,3,4,3,2,2,9,3,2,3,2,2,3,2,3,9,2,2,3,3,4,3,3,2,18,2,3,3,2,2,6,3,2,9,3,2,3,3,2,3,2,2,9,3,3,3,2,3,3,3,4,9,2,3,3,3,2,6,2,4,9,2,2,3,2,3,9,4,4,9,3,5,3,2,3,3,3,3,9,2,2,3,2,3,3,4,3,9,3,2,6,3,3,3,3,3,9,2,3,3,2,2,3,2,3,9,2,2,3,3,2,3,6,3,9,2,2,3,2,3,3,2,2,18,2,2,3,3,2,3,2,2,9,2,2,6,2,2,3,3,2,9,2,2,3,2,2,3,3,2,9,2,3,6,3,3,6,4,3,9,3,2,3,3,4,3,2,4,18,3,3,3,3,2,3,3,2,9,2,3,3,3,3,3,3,3,9,3,2,6,3,2,3,2,5,9,2,3,3,3,4,3,4,3,9,2,3,3,2,3,3,2,3,18,2,3,3,2,3,3,3,2,18,3,2,3,4,2,3,3,3,9,2,4,3,5,2,3,3,3,9,3,2,6,2,2,3,3,3,9,2,3,3,2,3,6,2,2,9,3,2,3,4,3,3,2,4,9,3,4,3,2,2,3,3,2,9,4,2,3,3,2,3,3,2,9,2,3,6,2,2,3,3,3,9,3,3,3,2,4,3,2,2,9,2,7,6,2,3,3,4,3,9,2,2,3,3,5,3,2,2,18,4,3,3,3,2,3,2,2,9,2,2,3,3,3,3,2,2,9,2,2,6,2,2,3,2,2,9,3,2,3,2,2,6,2,2,9,5,3,3,3,3,3,3,4,9,3,3,3,6,2,3,2,2,9,4,2,3,3,3,3,2,2,9,2,3,6,2,2,3,2,2,9,3,2,3,3,4,6,3,4,9,3,2,3,3,3,3,4,3,9,3,2,3,4,2,3,2,3,18,3,3,3,2,2,3,3,3,9,2,4,3,2,2,3,3,2,9,3,5,3,2,3,3,2,3,9,2,3,3,3,2,6,2,3,9,2,3,3,3,3,3,2,4,9,3,3,3,3,3,6,3,2,9,4,2,6,3,2,6,6,2,9,5,2,6,3,4,6,3,3,9,3,3,3,2,2,3,3,2,9,3,2,3,2,2,3,4,2,9,3,3,3,2,3,3,2,3,18,2,2,6,3,3,3,3,3,9,4,4,3,3,2,3,3,3,9,2,3,3,2,2,3,7,2,9,3,2,3,3,2,6,4,3,9,2,3,3,4,3,6,2,6,9,2,2,3,4,2,3,3,4,9,4,3,3,2,2,3,2,3,9,2,3,6,2,2,6,2,2,9,3,3,3,2,2,3,2,2,9,3,3,3,5,3,3,4,2,9,4,2,3,3,3,3,2,2,18,3,2,3,2,2,3,2,3,9,3,6,3,3,2,3,4,3,9,2,4,3,2,2,3,3,3,9,3,3,3,2,3,6,3,3,9,3,2,3,2,3,3,2,4,9,2,3,3,3,3,3,2,3,9,4,2,3,2,4,3,3,2,9,3,3,6,2,5,3,2,2,9,3,2,3,2,4,3,2,3,9,3,2,3,3,2,6,4,4,9,3,3,3,2,2,3,2,3,18,3,2,3,2,3,3,2,2,9,5,4,3,2,2,3,3,3,9,2,2,3,4,3,3,3,2,9,2,2,3,3,2,6,2,2,9,3,5,3,3,2,3,2,2,9,3,4,3,3,3,6,2,3,9,2,2,6,3,2,3,3,3,9,3,2,12,3,2,3,2,2,9,3,2,3,3,4,3,4,2,9,3,2,3,3,3,3,4,3,9,3,5,3,2,2,3,3,3,18,2,3,3,3,3,6,2,3,9,3,2,3,2,2,3,3,2,9,3,3,3,2,2,3,3,4,9,3,2,3,3,3,6,5,3,9,4,3,3,3,2,3,3,4,9,3,3,3,3,3,3,2,3,9,4,2,3,2,4,6,3,3,9,2,3,6,3,2,3,3,3,27,2,2,6,3,2,3,3,1,9,2,3,3,2,3,3,2,2,9,2,3,3,2,3,3,2,2,18,2,3,3,3,3,3,2,3,9,3,4,3,2,3,3,2,5,9,2,3,3,4,2,3,2,3,9,2,2,3,2,3,6,2,3,9,3,3,6,2,3,3,3,4,9,3,3,3,2,2,3,3,2,9,2,3,3,5,3,3,2,2,9,4,3,6,3,2,3,2,2,9,3,2,3,2,2,3,2,3,9,2,2,6,3,2,3,4,3,9,2,3,3,4,2,3,2,3,18,3,3,3,3,3,3,2,7,9,2,2,12,3,3,3,3,3,9,4,3,3,6,3,3,3,2,9,2,3,3,2,3,6,2,3,9,3,3,3,3,5,3,2,4,9,2,3,3,2,2,3,3,2,9,2,3,3,4,3,3,2,2,18,2,2,6,3,2,3,4,3,9,3,1,3,3,4,3,2,2,9,5,2,3,3,2,3,2,3,9,2,2,3,2,3,3,3,4,18,3,2,6,2,3,3,2,2,9,3,4,3,2,3,3,2,2,9,3,2,3,4,2,6,3,3,9,3,4,3,3,4,6,3,2,9,2,2,3,3,2,3,2,4,9,2,2,3,3,3,3,2,3,9,2,2,3,2,2,3,2,3,9,2,6,6,3,2,3,2,3,9,2,2,3,3,4,6,3,2,9,3,3,3,3,2,3,4,2,9,3,3,3,3,3,3,2,2,18,2,3,3,2,3,6,5,2,9,3,4,3,3,3,3,3,4,9,3,2,3,2,3,3,3,3,9,3,2,3,3,2,6,2,3,9,2,2,3,2,4,3,3,2,9,3,3,6,7,3,3,3,2,9,4,2,6,6,3,3,2,3,9,2,3,6,4,2,3,3,3,9,2,3,3,2,4,3,4,2,9,4,3,3,5,3,3,4,5,9,3,2,3,2,2,3,2,3,18,2,3,3,2,2,3,2,2,9,2,2,3,3,2,6,3,3,9,2,2,3,2,2,3,2,2,9,3,3,3,5,2,6,3,2,9,2,4,6,3,3,3,2,4,9,2,3,3,2,3,3,3,4,9,2,3,3,3,2,3,3,3,9,3,3,6,2,3,6,2,3,9,2,2,3,2,4,3,4,2,9,3,2,3,2,2,3,4,2,9,3,3,3,3,3,3,2,2,18,2,2,3,2,3,3,2,2,9,2,4,3,2,5,3,3,3,9,3,3,3,4,2,3,2,3,9,3,2,3,2,2,6,2,3,9,3,2,3,2,3,3,3,4,9,3,2,3,3,2,3,3,2,9,6,2,3,2,2,3,2,3,9,2,2,6,2,3,3,3,4,9,3,3,3,2,4,3,3,2,9,3,3,3,3,3,3,4,3,9,2,2,3,2,2,6,4,2,18,4,3,3,3,3,3,3,3,9,2,2,3,3,3,3,2,2,9,3,3,3,2,3,3,3,3,9,2,2,3,2,2,6,2,2,9,3,5,3,3,2,3,2,4,9,2,2,3,3,2,3,2,2,9,2,2,3,3,5,3,2,3,9,3,2,6,3,2,3,3,2,9,4,4,3,2,4,3,5,2,9,3,2,3,2,2,3,4,3,9,2,2,3,3,3,3,3,4,18,2,2,3,2,2,3,3,2,9,3,4,3,2,3,3,2,4,9,2,3,6,4,3,3,2,3,9,2,2,3,3,3,6,3,3,9,3,2,3,3,2,3,3,4,9,3,3,6,2,3,3,3,2,9,4,2,6,2,2,3,3,5,9,2,3,6,2,3,3,3,2,9,2,3,6,2,4,3,3,2,9,2,3,6,2,3,3,2,2,9,3,3,3,3,2,3,2,2,18,3,2,3,5,3,3,3,2,9,2,4,3,2,2,3,3,2,9,3,3,3,4,3,3,2,2,9,3,3,3,2,9,6,2,2,9,4,3,3,3,3,3,3,2,9,3,3,3,3,2,3,2,3,9,4,3,3,3,2,3,2,3,9,3,3,6,3,3,3,3,2,9,2,2,3,2,4,3,2,3,9,3,2,3,2,6,3,2,2,9,2,3,3,4,4,3,3,3,18,4,2,3,2,2,3,3,2,9,2,2,3,3,3,3,2,4,9,2,2,3,4,3,3,3,2,9,5,2,3,2,3,12,3,2,9,3,2,6,2,3,3,3,6,9,3,4,3,3,2,3,2,3,9,4,3,3,2,2,3,2,3,9,4,3,6,3,3,6,2,3,9,2,3,3,3,4,3,2,3,27,2,3,3,3,3,3,4,3,9,3,3,3,2,2,6,2,3,18,3,2,3,3,3,3,2,4,9,3,6,3,3,3,3,2,2,9,3,2,3,4,2,3,2,2,9,2,3,3,2,2,12,3,4,9,3,3,3,2,2,3,4,2,9,2,3,3,2,2,3,5,2,9,2,3,3,3,3,3,3,3,9,3,3,6,2,3,3,3,3,9,7,3,3,4,2,3,3,2,18,2,2,3,3,3,3,4,2,9,2,3,6,2,2,3,3,3,18,2,3,3,3,3,3,2,3,9,3,4,3,2,2,3,2,2,9,2,3,3,4,3,3,2,2,9,2,2,3,6,2,6,2,5,9,3,3,3,2,3,3,3,2,9,3,3,3,2,2,6,2,4,9,4,4,3,2,3,3,3,2,9,2,2,6,2,3,6,4,4,9,2,3,3,5,2,3,3,2,9,3,4,3,3,2,3,2,3,9,3,2,3,3,3,3,2,3,18,3,2,3,3,2,3,5,3,9,3,2,3,2,2,3,3,2,9,2,3,3,4,3,3,2,3,9,2,2,3,3,3,6,2,2,9,3,3,3,4,2,3,3,4,9,2,3,3,3,2,3,2,2,9,4,2,3,3,5,3,2,3,9,4,3,6,4,3,3,2,3,9,2,2,3,3,2,3,3,3,9,2,2,3,4,3,3,2,3,9,7,3,3,3,2,3,3,2,18,5,2,3,2,3,3,3,2,9,4,2,3,3,2,9,4,3,9,2,2,3,4,2,3,3,3,9,3,3,3,2,3,6,3,2,9,2,2,3,2,3,6,2,4,9,2,3,3,3,2,3,3,3,9,6,3,3,2,2,3,3,2,9,2,2,6,2,3,3,2,2,9,3,3,3,2,4,3,2,2,9,3,5,3,3,3,6,4,3,9,3,3,3,2,4,3,3,3,18,2,3,3,2,2,3,3,2,9,3,4,6,3,2,3,2,3,9,3,3,3,4,2,3,5,3,9,2,3,3,3,2,6,3,2,9,2,4,3,2,3,3,2,2,9,2,3,6,3,3,3,3,2,9,4,2,3,2,2,3,3,3,9,3,3,6,3,2,3,2,2,9,2,3,6,2,4,3,2,5,9,3,2,3,4,2,3,2,4,9,3,2,3,2,2,3,3,3,18,2,3,3,2,3,3,3,5,9,3,4,3,3,3,3,3,3,9,3,2,3,4,3,3,4,2,9,2,3,3,3,2,6,2,2,9,3,2,3,2,3,3,3,4,9,3,3,3,5,4,3,2,2,9,4,7,3,3,4,3,2,2,9,2,2,6,3,2,6,3,2,9,3,2,3,3,4,3,3,3,9,2,3,3,3,4,3,4,3,9,4,3,3,3,3,3,2,2,18,2,2,3,2,2,3,3,2,9,3,2,6,2,3,3,2,3,9,3,2,3,2,2,3,3,2,9,3,3,6,2,5,12,2,4,9,2,3,3,3,2,3,3,2,9,3,2,3,2,2,3,2,3,9,4,2,3,2,3,3,3,3,9,3,2,6,2,3,3,3,2,9,5,3,3,3,2,3,2,3,9,3,3,3,3,2,3,4,2,9,3,3,6,2,2,3,2,2,18,3,2,3,2,3,3,4,2,9,2,4,3,3,3,6,3,3,9,2,2,3,4,2,3,4,2,9,2,3,3,3,3,6,2,3,9,2,2,3,3,2,3,2,4,9,2,2,3,3,3,3,3,3,18,2,5,3,2,3,3,3,3,9,3,2,6,2,2,3,3,3,9,3,2,3,2,2,3,2,4,9,2,2,3,3,2,3,4,3,9,3,3,3,4,4,3,7,2,18,3,3,3,3,2,3,3,3,9,2,2,3,3,3,3,2,2,9,2,3,3,2,3,3,2,3,9,2,2,6,2,2,6,4,2,9,3,3,6,4,6,3,3,2,9,3,3,3,2,2,3,2,2,9,2,2,3,2,3,3,2,4,9,2,2,6,3,3,3,3,2,9,2,4,3,3,4,3,2,5,9,3,3,3,2,2,3,4,3,9,2,3,3,2,2,3,4,3,18,2,3,3,2,3,3,3,3,9,3,4,3,3,3,3,3,2,9,3,3,3,6,3,3,3,3,9,4,3,3,2,3,6,2,3,9,3,2,3,3,2,3,3,4,9,2,3,3,2,3,3,3,3,9,4,2,3,2,3,3,2,3,9,3,2,6,2,3,3,2,2,9,2,3,6,3,4,3,3,2,9,3,3,3,2,2,3,4,3,27,3,2,3,2,3,3,3,3,36,1,2,3,3,5,3,3,2,9,2,2,3,2,3,3,3,2,9,2,3,3,4,2,3,2,2,9,10,3,3,3,3,6,4,3,9,3,2,9,3,2,3,2,4,9,5,2,3,2,3,3,2,3,9,4,2,3,3,3,3,2,2,9,3,3,6,3,3,3,2,3,9,2,3,6,3,4,3,3,3,9,2,3,3,2,2,6,2,3,9,2,2,3,3,2,3,3,3,18,2,2,3,2,2,3,3,3,9,2,4,3,3,4,3,3,3,9,3,2,3,2,2,3,3,2,9,3,5,3,2,3,6,3,3,9,3,3,3,6,2,3,2,4,9,3,2,3,4,3,3,3,3,9,4,2,3,2,2,3,3,2,9,2,3,6,3,3,3,5,2,9,2,2,3,2,6,3,2,2,9,2,2,3,3,3,3,2,3,9,3,2,6,2,2,3,3,2,18,2,3,3,2,2,3,3,2,9,3,4,6,2,2,3,2,3,9,2,3,3,4,4,3,3,2,9,2,2,3,3,3,6,3,3,9,3,4,3,3,3,3,1,2,9,3,2,3,3,2,3,3,5,9,4,3,3,2,2,3,2,2,9,3,4,6,3,2,3,3,3,9,4,3,3,2,4,6,2,7,9,3,2,3,3,3,3,4,3,9,3,2,3,5,3,6,3,3,18,3,5,3,2,2,6,2,2,9,2,4,6,3,3,3,2,2,9,2,2,3,4,3,3,2,3,9,2,2,3,3,2,6,2,2,9,2,2,3,3,2,3,2,2,9,2,2,3,2,2,3,3,4,9,4,2,3,3,3,3,2,2,9,3,3,6,3,3,3,4,3,9,2,3,3,2,6,6,3,2,9,2,3,3,3,3,3,2,3,9,3,3,3,3,3,3,3,3,18,3,6,3,3,2,3,2,4,9,2,4,3,2,2,3,3,4,9,5,3,3,4,2,3,2,3,9,3,2,3,3,3,6,2,3,9,3,2,3,2,2,3,3,4,9,3,3,3,2,2,3,3,2,9,2,3,3,2,3,6,3,2,9,2,3,6,3,2,3,2,2,9,2,3,3,3,4,3,4,2,9,2,3,3,2,2,3,4,2,9,3,2,3,3,2,3,3,2,18,2,5,3,2,2,3,2,3,9,4,4,3,4,3,3,2,3,9,2,3,3,8,2,3,3,2,9,2,3,3,2,3,6,2,2,9,2,2,3,3,3,3,5,4,9,3,3,3,2,2,3,2,3,9,4,2,3,3,3,3,3,3,9,3,3,6,2,2,3,2,2,9,2,4,12,3,4,3,3,3,9,2,3,6,3,2,3,6,2,9,4,4,3,2,2,3,3,2,18,2,3,3,2,4,3,3,2,9,3,2,6,2,2,3,2,2,9,2,2,3,4,2,3,2,6,9,4,3,6,3,2,6,3,2,9,2,3,3,3,3,3,2,2,9,3,2,3,3,3,3,2,3,9,2,2,3,2,2,3,3,2,9,2,2,6,5,3,3,2,3,9,3,3,3,3,4,3,3,3,9,3,3,3,4,3,3,2,3,9,3,2,6,2,2,3,2,2,18,3,3,3,3,3,3,2,3,9,3,2,3,2,4,3,3,2,9,3,2,3,2,2,3,2,3,9,3,3,3,3,2,6,3,3,9,2,3,6,3,3,3,3,4,9,2,2,3,3,5,3,4,3,9,4,2,3,3,3,3,2,3,9,2,3,6,3,2,3,2,3,9,2,3,3,2,4,3,2,2,9,3,3,3,3,3,3,2,2,9,5,2,3,2,4,3,2,3,18,3,3,3,3,2,3,3,3,9,2,2,3,6,2,3,4,3,9,2,3,3,2,2,3,2,3,9,3,2,3,3,4,6,2,2,9,3,3,3,3,2,3,2,2,9,3,2,3,5,3,6,3,3,9,4,2,3,2,3,3,2,2,9,2,2,6,2,2,3,2,3,9,3,5,3,3,2,3,2,3,9,3,3,3,3,4,3,4,2,9,2,3,3,3,3,3,2,2,18,2,3,3,2,2,3,4,2,9,2,4,6,2,3,3,5,3,18,2,2,3,4,3,3,3,2,9,3,3,3,3,3,6,2,2,9,2,3,3,3,3,3,3,4,9,2,2,3,2,3,3,3,3,9,4,3,6,3,2,6,3,3,9,3,3,6,3,3,6,2,3,9,3,2,3,3,2,3,2,2,9,2,3,3,3,2,3,2,2,9,4,3,3,2,2,3,3,5,27,2,3,3,2,7,6,2,2,9,3,2,3,2,3,3,3,2,9,3,2,3,2,2,3,3,3,9,3,3,3,3,3,6,4,3,9,3,3,3,5,2,3,2,4,9,2,3,3,3,4,3,2,3,9,2,2,3,2,2,6,3,3,9,2,2,6,2,2,3,2,4,9,2,3,3,3,2,3,2,2,9,3,3,3,3,3,3,4,3,9,3,2,3,3,3,3,2,2,18,3,2,3,2,3,3,3,4,9,3,4,3,3,3,3,3,2,9,3,2,3,4,5,3,2,2,9,3,3,3,3,2,6,3,3,9,2,3,3,3,3,3,2,2,9,2,3,3,3,2,6,2,3,9,4,3,3,2,3,3,2,2,9,5,3,6,3,2,3,3,3,9,2,2,3,5,4,3,2,2,9,2,2,6,2,3,3,2,2,9,3,3,3,3,3,3,2,3,18,3,3,3,3,3,6,3,3,9,3,4,3,2,2,3,3,2,9,3,3,3,2,2,6,3,3,9,3,2,3,4,2,6,3,3,9,3,2,3,3,3,3,3,4,9,7,6,3,3,3,3,3,2,9,4,3,3,3,2,3,3,2,9,2,3,6,3,2,3,2,3,9,3,2,3,3,2,3,3,3,9,3,2,3,2,2,3,6,2,9,3,3,3,2,2,3,3,3,18,2,3,3,2,3,3,2,2,9,2,4,3,2,2,3,2,3,9,4,2,3,4,3,3,3,4,9,2,4,6,3,2,6,3,2,9,3,3,3,2,2,3,2,2,9,2,2,3,3,3,3,2,3,9,4,3,3,2,2,3,3,3,9,3,3,6,2,2,3,3,5,9,3,3,3,2,4,3,2,3,9,3,2,3,4,3,3,2,2,9,3,2,3,2,3,12,2,2,18,3,3,6,3,3,3,2,2,9,3,6,3,5,3,3,2,2,9,2,2,3,4,3,3,3,2,9,4,3,3,3,3,6,3,2,9,3,2,3,2,3,3,2,4,9,3,2,3,3,2,3,3,4,9,2,4,3,3,2,3,3,2,9,3,2,6,3,3,3,4,2,9,2,3,3,4,4,3,2,2,9,3,3,3,3,3,9,4,2,9,3,2,3,3,5,3,2,3,18,2,2,3,3,2,3,2,3,9,3,2,3,2,2,3,2,3,9,2,3,3,4,3,6,3,3,9,3,3,6,2,3,6,3,3,9,5,2,3,3,2,6,2,2,9,2,2,3,2,4,3,2,3,9,4,2,3,3,4,3,2,2,9,2,2,6,3,2,3,3,3,9,2,2,3,2,2,6,3,2,9,2,3,3,2,3,6,2,3,9,2,2,3,3,2,3,3,3,18,2,2,3,3,2,3,3,3,9,2,4,3,2,2,3,3,2,9,2,5,3,2,3,6,2,2,9,3,2,6,2,4,6,2,3,9,3,2,3,2,2,3,2,4,9,3,3,3,2,2,3,2,2,9,2,3,3,2,2,3,5,4,9,3,2,6,2,3,3,5,3,9,3,2,3,3,4,3,3,3,9,3,3,3,2,3,3,4,2,9,4,3,3,2,3,3,2,2,18,3,2,6,3,3,3,3,2,9,6,2,3,2,3,3,2,2,9,2,2,3,2,2,3,3,2,9,2,7,3,3,2,6,2,3,9,3,2,3,2,3,3,3,6,9,4,3,3,2,2,3,3,3,9,4,2,3,3,3,3,2,2,9,3,3,6,3,2,3,3,4,9,3,2,3,3,4,3,2,2,9,3,3,3,5,3,3,4,4,9,3,3,3,2,2,3,2,3,18,4,2,3,2,3,3,3,2,9,3,4,3,2,3,3,2,3,9,2,2,6,6,3,3,2,2,9,2,2,3,2,2,6,3,2,18,3,3,3,2,3,3,2,4,9,3,2,3,2,4,3,2,3,9,4,4,3,3,3,3,3,3,9,2,3,6,2,5,6,3,3,9,2,2,6,3,2,3,2,2,9,2,3,3,3,3,3,4,3,9,3,3,3,2,3,3,2,3,18,2,3,3,2,2,3,2,2,9,5,2,3,2,3,3,2,2,9,4,3,3,4,2,3,2,2,9,3,2,3,3,2,6,3,2,9,3,4,6,2,2,3,3,10,9,4,2,3,4,2,6,2,2,9,4,2,3,2,2,3,2,3,9,3,2,6,3,3,3,7,3,9,2,3,3,3,2,3,3,2,9,2,3,3,2,3,3,4,2,9,2,5,3,3,3,3,3,3,18,3,2,3,3,3,3,3,3,27,3,4,3,2,3,3,3,3,9,3,3,3,2,4,3,2,2,9,2,4,3,2,2,6,5,2,9,3,3,3,4,2,3,2,4,9,3,2,6,3,3,3,3,2,9,4,3,3,3,2,6,3,2,9,3,2,12,3,2,3,2,2,9,2,3,6,2,4,3,2,3,9,3,3,3,3,2,3,4,3,9,3,3,3,2,2,3,2,3,18,3,3,3,2,4,3,2,3,9,3,2,3,3,2,3,2,5,9,2,2,3,2,2,3,2,3,9,2,3,3,2,3,6,3,2,9,2,3,3,4,3,6,3,4,9,3,2,3,3,2,3,2,2,9,2,3,3,6,3,3,3,2,9,3,2,6,3,2,3,3,2,9,3,3,3,2,4,3,2,3,9,2,2,3,3,2,3,4,2,9,3,2,3,3,3,3,2,2,18,3,4,3,3,2,3,3,2,9,3,4,9,3,4,3,4,3,18,2,3,3,4,2,3,2,3,9,3,3,3,3,2,6,2,4,9,3,3,3,3,5,3,2,4,9,3,3,3,2,3,3,3,2,9,2,3,3,2,2,3,3,3,9,2,2,6,2,4,3,3,2,9,2,2,3,3,2,3,2,3,9,5,3,3,2,2,6,2,3,9,3,2,3,3,2,3,3,2,18,3,2,6,3,2,6,3,3,9,2,2,3,2,2,3,3,2,9,2,3,3,4,2,6,2,3,9,2,3,3,3,3,6,3,3,9,3,2,3,3,3,3,3,2,9,2,3,6,3,4,3,3,2,9,2,3,3,3,3,3,4,3,9,2,5,6,2,2,3,2,3,9,3,2,3,2,4,3,3,2,9,3,3,3,2,3,3,4,2,9,3,3,6,2,3,3,2,3,18,3,2,3,2,2,3,5,3,9,3,4,3,3,3,3,3,2,9,2,3,3,2,3,3,3,2,9,4,3,3,3,2,6,2,4,9,3,2,3,3,2,3,2,4,9,2,2,6,2,3,3,3,7,9,4,3,3,2,2,3,2,2,9,3,3,6,2,3,3,2,2,9,2,2,3,2,4,3,3,3,9,2,2,3,3,4,3,2,5,9,5,4,3,3,3,3,3,2,18,2,3,3,3,3,3,2,4,9,2,4,3,2,2,3,2,2,9,3,2,3,4,2,3,3,1,9,2,2,3,5,3,6,3,3,9,3,3,3,2,2,3,4,4,9,2,2,3,3,4,3,2,2,9,4,2,3,2,3,3,3,2,9,2,2,6,2,3,3,2,3,9,3,2,3,2,4,3,2,3,9,4,3,3,3,2,6,2,3,9,3,3,3,2,2,3,2,3,18,2,2,3,2,2,3,3,3,9,2,2,3,3,5,3,2,2,9,3,3,3,4,3,6,2,3,9,2,2,3,4,2,6,3,2,9,3,2,3,2,3,3,3,6,9,2,3,3,3,2,3,2,3,9,6,4,3,3,2,3,2,2,9,3,3,6,4,2,3,3,2,9,3,2,3,2,2,3,3,2,9,2,3,3,2,2,3,4,2,9,2,3,3,7,2,6,3,4,18,3,2,3,2,2,3,3,3,9,3,4,3,3,2,3,3,3,9,3,2,3,4,2,3,2,3,9,2,3,6,2,3,6,2,3,9,3,5,3,3,2,3,2,4,9,3,4,3,2,2,3,2,2,18,4,3,3,3,3,3,3,2,9,3,5,6,2,2,6,3,2,9,2,2,3,3,4,3,5,3,9,3,3,3,2,2,3,4,2,9,3,5,3,2,3,6,2,2,18,3,3,3,4,3,3,2,2,9,2,4,3,3,3,3,3,2,9,3,3,6,4,2,3,3,3,9,3,1,3,3,3,6,2,3,9,2,2,3,2,3,3,3,4,9,3,3,3,2,2,3,2,3,9,4,4,3,2,3,3,2,5,9,3,2,6,2,3,3,2,2,9,2,2,3,3,4,3,2,3,9,3,3,3,2,3,3,2,3,9,3,2,3,3,3,3,2,3,18,3,3,3,5,2,3,4,4,9,2,2,3,3,2,6,3,2,9,2,2,3,2,3,3,2,3,9,2,2,3,4,2,6,3,2,9,3,3,3,2,3,3,3,4,9,2,2,3,3,3,6,3,3,9,2,4,3,2,2,3,3,3,9,3,3,6,3,2,3,2,2,9,3,2,3,2,4,3,3,3,9,2,2,3,3,5,3,4,3,9,2,2,3,2,2,3,2,2,18,2,3,3,2,2,3,2,3,9,2,2,3,2,2,3,3,3,27,3,3,3,4,3,3,4,3,9,5,3,3,2,3,6,3,2,9,3,2,12,2,2,3,2,2,9,4,3,3,3,4,3,3,3,9,6,2,3,3,2,6,2,3,9,2,2,6,2,2,6,3,3,9,3,3,3,2,4,3,3,2,9,4,2,3,3,2,3,4,2,9,2,3,3,2,3,3,2,4,18,3,3,3,3,3,3,3,3,9,2,6,3,2,3,3,3,2,9,3,2,3,4,4,3,2,3,9,3,3,3,2,2,6,3,2,9,2,2,3,4,2,3,3,4,9,4,3,3,3,3,3,5,2,9,4,3,3,3,2,3,2,4,9,3,2,6,3,2,3,2,2,9,3,2,3,3,8,3,3,3,9,2,3,6,3,2,3,2,2,9,3,2,6,2,3,3,2,3,18,2,3,3,2,3,3,3,3,9,2,4,3,2,3,3,2,2,9,3,3,3,4,3,3,3,4,9,3,2,3,3,3,6,3,5,9,2,2,3,4,2,3,4,4,9,4,2,3,2,2,3,2,2,9,4,2,3,2,3,3,3,2,9,4,3,6,3,2,3,3,2,9,2,3,3,5,4,3,3,2,9,2,3,3,2,3,3,2,2,9,3,2,3,2,3,3,2,2,18,3,3,3,2,3,6,3,2,9,3,4,3,5,3,3,2,3,9,2,4,3,4,4,3,2,3,9,3,2,3,2,2,6,2,3,9,3,2,3,2,3,3,2,2,9,2,2,3,2,2,3,2,3,9,4,2,3,2,5,3,2,3,9,3,2,12,4,3,3,3,2,9,2,3,3,3,2,3,3,2,9,3,3,3,4,2,3,2,3,9,3,3,6,2,3,3,3,3,18,5,2,3,2,3,3,2,3,9,3,2,3,2,3,3,2,2,9,7,3,3,4,3,3,2,3,9,3,3,3,3,2,6,3,3,9,2,3,3,2,2,6,2,4,9,2,3,3,3,3,3,2,2,9,4,2,3,3,3,3,4,4,9,3,4,6,4,4,3,2,3,9,3,3,3,2,2,3,2,2,9,4,5,3,2,2,3,2,3,9,2,2,3,3,2,6,3,2,18,2,2,3,3,2,3,3,2,9,2,2,3,2,2,3,2,3,9,3,2,3,4,2,6,5,3,9,3,2,3,2,2,6,3,2,9,3,3,3,2,6,3,3,4,9,3,3,3,2,3,3,3,2,9,4,2,3,2,3,3,2,3,9,3,3,6,3,3,3,4,3,9,2,2,3,2,4,3,3,3,9,3,3,3,3,5,3,2,2,9,3,2,3,2,3,3,3,2,18,3,2,6,2,3,3,2,5,9,3,4,3,2,2,6,3,3,9,3,3,3,2,2,3,4,3,9,3,2,3,2,3,6,3,3,9,2,3,3,3,2,3,3,2,9,3,2,3,5,2,3,3,3,9,2,2,3,3,2,9,2,2,9,3,2,6,3,3,3,2,3,18,2,3,3,3,4,3,3,3,9,2,2,3,3,3,3,8,2,9,3,2,3,3,2,3,3,3,18,2,3,3,2,4,3,2,2,9,2,4,3,3,2,3,3,3,9,2,3,3,4,3,3,2,3,9,3,2,3,2,5,6,3,2,9,2,2,3,3,3,3,2,4,9,3,2,3,3,2,3,2,2,9,4,2,3,2,2,3,3,4,9,2,3,6,2,2,3,2,3,9,5,4,6,2,4,3,3,3,9,2,2,6,4,2,3,2,3,9,3,2,3,3,2,3,3,3,18,2,3,3,2,3,6,2,4,9,2,4,3,3,3,6,3,3,9,3,2,3,2,3,3,3,3,9,2,2,3,3,3,6,3,3,9,2,3,3,3,3,3,3,2,9,2,2,3,2,2,3,2,3,9,2,5,3,2,2,12,3,3,9,4,3,6,2,2,3,3,2,9,2,2,3,4,6,3,3,2,9,3,2,3,3,3,3,2,3,9,2,2,3,3,2,3,5,2,18,3,7,3,2,2,3,3,3,9,4,4,3,2,3,3,2,3,9,3,3,3,4,3,3,2,3,9,3,3,3,3,3,6,3,3,9,3,2,6,2,2,3,2,4,9,3,3,3,3,3,6,3,2,9,2,3,3,3,3,3,2,2,9,2,2,6,4,2,3,3,2,9,2,2,3,3,4,6,3,5,9,2,4,3,2,2,15,4,3,9,3,2,3,2,5,3,3,2,18,2,2,3,3,2,6,2,2,9,2,2,3,2,3,6,3,3,9,3,2,3,6,3,6,2,3,27,3,3,3,3,3,6,3,3,9,2,2,3,3,2,3,2,4,9,2,3,3,3,2,3,2,3,9,2,3,6,3,3,3,2,3,9,3,2,6,2,3,3,2,3,9,2,2,3,3,4,3,2,4,9,2,3,3,3,3,3,2,3,9,2,2,3,2,3,3,2,2,18,3,3,3,4,5,3,3,3,9,3,4,3,3,3,3,3,3,9,2,3,6,2,2,3,3,2,9,3,2,3,4,2,6,5,3,9,2,2,3,4,3,3,7,4,9,5,3,3,3,2,3,3,4,9,4,2,3,2,2,3,3,2,9,3,3,6,2,3,3,3,3,9,2,2,3,3,4,3,3,2,9,4,4,3,2,3,6,4,3,9,2,3,3,2,2,3,3,2,18,3,3,3,3,4,3,2,2,9,3,2,3,3,3,3,3,2,9,3,2,3,4,2,3,3,2,9,3,5,3,3,3,6,4,2,9,3,3,3,4,3,3,3,2,9,3,3,3,2,2,3,3,3,9,4,3,3,3,2,3,2,2,9,2,3,6,2,2,3,5,2,9,2,4,3,3,2,6,3,2,9,3,2,6,2,3,3,6,3,9,4,2,3,2,3,3,2,2,18,3,2,3,3,3,3,3,2,9,2,4,6,3,3,3,2,3,9,2,3,3,2,3,3,2,3,9,2,2,3,2,2,6,2,3,9,3,3,3,3,3,3,4,2,9,3,2,3,2,3,3,4,5,9,4,2,3,3,3,3,2,3,9,2,2,6,3,2,3,4,2,9,4,2,6,2,2,3,3,2,9,3,2,9,2,4,3,4,3,9,3,3,3,5,3,3,3,2,18,3,2,3,3,3,3,3,5,9,3,2,3,2,3,3,2,2,9,3,2,3,4,4,3,3,4,9,5,3,6,2,3,6,2,3,9,3,3,3,3,3,3,3,4,9,2,2,3,3,3,3,2,2,9,2,2,3,3,2,3,3,3,9,2,2,6,2,2,3,2,3,9,2,3,3,3,6,3,3,2,9,2,2,3,2,2,3,4,2,9,3,2,3,2,2,3,2,3,18,2,2,6,2,3,3,2,3,9,2,2,3,3,2,3,2,3,9,5,2,3,2,3,6,3,2,9,2,3,3,2,3,6,2,2,9,3,2,3,2,2,3,4,2,9,2,3,3,2,3,3,2,3,9,4,2,3,3,3,6,2,3,9,3,3,6,2,4,3,3,3,9,4,3,3,2,4,3,3,3,9,4,2,3,3,2,3,4,2,18,2,3,3,3,2,3,3,3,18,2,5,3,2,3,3,2,2,9,3,2,3,3,3,3,3,3,9,3,2,3,4,3,3,3,7,9,3,3,3,2,2,6,3,3,9,2,3,3,2,2,3,5,2,9,3,2,3,3,4,3,2,3,9,4,2,3,3,4,3,3,6,9,3,2,6,3,2,3,3,2,9,3,3,3,2,2,3,3,2,18,2,2,6,3,3,3,2,2,9,3,2,3,3,3,3,2,2,18,3,3,3,2,2,3,4,4,9,2,4,3,2,3,3,3,2,9,3,2,6,4,3,3,3,5,9,2,3,3,3,3,6,3,3,9,3,3,3,2,2,6,2,2,9,2,2,3,3,3,3,3,3,9,4,2,3,3,3,3,2,2,9,3,2,6,5,2,3,2,3,9,3,3,3,2,2,3,2,4,9,3,3,3,2,2,3,4,2,9,4,3,3,4,3,3,3,2,18,2,2,3,3,3,3,2,3,9,2,4,6,2,2,3,2,3,9,2,2,3,4,3,3,2,3,9,2,2,3,3,2,6,2,2,9,2,3,3,3,3,3,3,4,9,3,3,3,3,5,3,3,2,9,4,3,3,2,2,3,2,2,9,3,2,6,7,4,6,2,2,9,3,2,3,3,4,3,3,3,9,3,2,3,2,3,3,4,3,9,5,3,3,3,2,6,2,3,18,2,4,3,3,2,3,3,3,9,2,4,3,3,2,3,2,3,9,2,2,3,2,3,3,3,3,9,3,3,3,2,2,6,2,3,9,2,2,3,2,2,6,4,2,9,2,2,3,3,2,3,2,3,9,10,3,3,2,3,3,3,2,9,2,2,6,2,2,3,2,3,9,3,5,3,3,2,3,2,3,9,3,4,3,3,3,3,4,2,9,3,3,3,3,3,3,3,6,18,2,3,3,3,2,3,2,2,9,3,4,3,2,3,3,5,3,9,3,2,3,4,2,3,2,3,9,3,2,3,3,4,6,2,2,27,2,3,3,3,2,3,2,4,9,3,3,3,2,3,3,2,3,9,4,2,6,3,3,3,4,3,9,3,3,6,2,2,3,2,3,9,3,3,3,2,4,3,3,4,9,3,3,3,2,3,3,2,4,9,2,3,3,3,2,3,3,5,18,2,3,3,3,3,3,2,2,9,2,6,3,2,3,3,3,2,9,4,2,3,4,3,3,2,2,9,2,2,3,3,3,6,2,3,9,3,3,3,5,4,3,2,2,9,3,2,3,3,2,3,3,2,9,2,2,3,3,3,3,2,3,9,2,3,6,2,2,3,3,3,9,2,2,3,3,2,3,2,3,9,3,2,3,3,2,3,4,2,9,2,3,3,3,3,3,3,3,18,3,2,6,3,3,6,2,3,9,2,4,3,2,2,6,3,3,9,2,3,6,2,6,3,2,2,9,2,5,3,2,3,6,3,3,9,4,3,6,3,3,3,3,4,9,2,3,3,3,2,3,3,2,9,2,3,3,2,3,6,2,3,9,5,3,6,2,3,3,2,2,9,2,3,3,2,4,3,2,3,9,3,3,3,3,2,3,4,2,9,3,3,3,2,2,3,3,2,18,4,2,3,2,4,6,2,3,9,3,4,3,2,3,3,3,2,9,4,4,3,4,2,3,3,3,9,2,2,3,3,3,6,3,3,9,3,2,3,3,2,3,2,2,9,2,5,3,2,7,3,2,2,9,4,3,3,2,2,3,3,3,9,2,3,6,2,4,3,3,3,9,3,2,3,3,4,3,3,4,9,3,2,6,2,2,3,6,3,9,3,2,3,2,3,3,3,4,18,2,3,3,2,3,3,4,3,9,3,4,3,3,3,3,2,2,9,2,3,3,2,2,3,3,2,9,3,2,6,3,2,6,2,2,9,2,2,6,3,2,3,2,4,9,3,3,6,3,3,3,3,2,9,2,3,3,4,2,6,2,3,9,2,3,6,3,2,3,3,5,9,3,3,3,3,4,3,2,2,9,3,4,3,2,3,3,4,3,9,3,3,3,3,2,3,2,3,18,2,3,12,2,2,3,2,2,18,2,4,3,5,2,3,3,2,9,2,3,3,6,3,3,3,3,9,2,2,3,2,4,6,3,3,9,4,2,3,4,3,3,3,2,9,2,3,3,2,3,3,3,2,9,4,3,3,3,3,3,3,2,9,3,3,6,3,3,6,3,3,9,2,3,3,2,4,3,3,2,9,3,2,3,3,2,3,4,3,9,7,2,3,3,5,3,2,3,18,3,2,3,3,2,6,3,3,9,3,4,3,2,2,3,3,2,9,4,4,3,4,3,3,2,2,9,2,3,3,3,3,6,3,2,9,5,2,3,2,2,3,2,4,9,3,3,3,2,3,3,3,2,9,4,3,3,2,2,3,3,2,9,2,3,6,2,3,3,4,3,9,2,3,6,2,4,6,4,3,9,1,3,3,3,2,3,4,2,9,2,3,3,2,2,3,3,4,18,3,3,3,2,2,3,3,2,9,3,2,3,4,2,3,2,2,9,2,5,3,4,2,3,3,2,9,2,3,3,3,3,6,3,3,9,3,2,3,2,3,3,2,4,9,3,2,3,3,3,3,2,4,9,4,2,3,2,3,3,5,3,9,2,3,6,3,2,6,2,3,9,3,3,3,5,4,3,4,3,9,2,3,3,2,2,3,2,2,9,2,3,3,4,2,3,2,3,18,3,3,6,3,2,3,3,2,9,3,2,3,2,4,6,2,3,9,2,2,3,4,3,3,3,2,9,2,3,3,2,2,12,3,3,9,2,3,3,3,2,3,2,6,9,3,3,3,2,3,3,2,3,9,4,3,3,3,4,3,2,3,9,2,3,6,2,2,3,3,3,9,3,3,3,2,4,3,3,3,9,2,3,3,5,4,3,4,2,9,2,3,3,2,3,3,3,3,18,4,2,3,3,2,3,3,3,9,3,2,6,3,2,3,3,4,9,2,3,3,2,3,3,2,2,9,2,3,3,3,3,6,2,2,9,3,3,6,3,2,3,3,2,9,2,2,3,2,3,3,4,2,9,4,3,6,2,2,3,2,3,9,3,2,6,3,5,3,3,3,9,2,4,3,3,2,3,3,3,9,2,3,3,2,3,3,4,3,9,3,3,3,3,3,3,2,3,18,3,3,3,3,2,3,3,3,9,5,4,3,2,3,3,5,2,9,4,3,6,2,3,3,3,3,9,3,2,3,3,2,6,4,3,9,2,3,3,3,3,3,3,2,27,2,2,6,2,5,6,3,3,9,2,3,3,3,3,3,1,2,9,3,2,6,3,2,3,2,2,9,3,7,3,3,2,6,2,3,9,3,2,3,3,2,3,4,2,9,3,5,3,2,2,3,2,4,18,3,2,3,3,3,3,2,3,9,3,2,3,2,2,3,3,2,9,2,3,6,4,2,3,2,2,9,3,3,3,2,2,6,5,2,9,3,2,3,3,3,3,2,4,9,2,2,3,2,2,3,3,2,9,2,2,3,2,2,3,3,2,9,3,2,6,2,2,3,3,2,9,3,3,6,3,2,6,3,2,9,3,2,3,3,3,3,4,2,9,2,3,3,3,5,3,3,2,18,2,2,3,2,3,3,2,2,9,3,2,3,3,3,3,3,5,9,3,3,3,4,2,3,2,3,9,3,4,3,3,3,6,2,3,9,2,2,3,3,2,3,2,4,9,2,3,3,2,3,3,2,2,9,2,2,3,5,2,3,3,3,9,3,2,6,2,2,6,3,3,9,2,4,3,3,4,3,3,2,9,2,2,3,3,2,3,2,4,9,2,2,3,3,2,3,3,3,18,3,3,3,3,2,3,3,3,9,3,2,3,2,2,3,7,2,9,2,2,3,2,3,12,4,3,9,3,2,3,3,3,6,3,3,9,2,4,3,3,5,3,4,6,9,3,3,3,2,3,3,2,2,9,4,2,3,3,2,3,3,2,9,3,2,6,4,2,3,3,3,9,3,3,3,3,4,3,2,3,9,5,3,3,2,2,3,4,2,9,3,2,3,3,3,3,3,2,18,2,3,3,2,3,3,2,3,9,3,2,3,3,2,3,3,4,9,3,3,3,2,2,6,2,2,18,3,2,3,2,2,6,2,3,9,2,2,3,2,4,3,3,4,9,2,3,3,1,4,3,3,3,9,4,3,3,3,2,3,2,2,9,3,5,6,2,3,3,3,3,9,2,2,3,2,2,3,3,3,9,2,2,3,2,2,3,4,2,9,3,3,3,3,3,3,4,2,18,3,3,3,2,3,6,5,2,9,3,2,3,2,2,3,2,2,9,2,3,3,4,3,3,3,2,9,3,4,3,3,2,6,2,3,9,3,3,3,2,2,3,3,4,9,2,2,6,3,3,3,3,2,9,2,3,9,4,3,3,2,3,9,4,2,6,2,3,3,2,2,9,3,2,3,2,4,3,3,3,9,2,3,3,3,2,3,4,6,9,2,2,3,2,2,3,5,3,18,3,3,3,3,2,3,3,3,9,3,2,3,2,3,3,4,2,9,2,2,3,4,2,3,3,3,9,2,2,3,6,2,6,2,3,9,2,4,3,2,2,3,3,4,9,4,2,3,2,2,3,3,3,9,4,3,6,3,3,3,2,3,9,2,3,6,3,2,3,3,3,9,2,2,3,2,4,3,2,3,9,3,3,3,3,2,3,4,3,9,3,2,3,3,2,3,2,3,18,2,2,3,3,2,3,3,2,9,3,4,6,2,5,3,2,2,9,2,3,3,4,2,3,2,3,9,3,2,3,2,3,12,4,3,9,4,3,3,2,2,3,3,2,9,3,3,3,2,3,3,3,3,9,6,3,3,2,2,3,2,3,9,2,3,6,2,2,3,3,2,9,3,2,3,2,4,3,3,2,9,4,2,3,4,3,3,2,2,9,3,3,3,3,3,6,3,7,18,3,3,3,3,3,3,2,3,9,2,4,3,2,3,6,3,6,9,3,3,3,4,2,3,3,4,9,3,2,3,3,5,6,3,4,9,2,5,3,3,3,3,3,4,9,3,2,3,3,3,3,2,2,9,4,3,3,3,4,3,2,3,9,3,4,6,3,3,3,3,5,9,3,2,3,2,4,3,5,2,9,3,3,3,2,3,3,2,2,9,2,2,3,2,2,6,3,2,18,3,2,3,3,3,3,3,2,9,2,2,3,3,2,3,2,3,9,3,2,6,2,2,3,2,3,9,2,4,6,3,3,12,3,3,9,4,2,3,2,3,3,3,2,9,2,2,3,3,2,3,2,3,9,4,3,3,3,2,3,2,5,9,2,3,6,3,3,3,2,2,9,2,2,3,4,4,6,3,3,9,3,3,3,3,2,3,4,3,9,3,2,3,3,2,3,2,2,18,3,2,3,5,3,3,4,2,9,2,2,3,3,2,3,2,3,9,2,3,3,4,3,3,3,3,9,3,3,3,3,2,6,3,2,9,3,2,6,7,2,3,3,2,9,3,2,3,2,2,3,2,2,27,4,4,3,3,4,3,2,3,9,2,3,6,2,2,3,3,2,9,2,3,3,2,4,3,2,2,9,2,3,3,3,5,3,4,3,9,3,2,3,3,2,3,2,3,18,2,2,3,2,2,3,2,2,9,3,4,3,2,2,6,2,2,9,2,2,3,4,3,3,3,2,9,5,3,3,2,3,6,3,3,9,2,3,3,3,4,3,3,4,18,2,3,3,2,2,3,3,3,9,4,3,3,2,3,3,2,2,9,2,3,6,2,2,6,3,2,9,3,3,3,2,4,3,3,2,9,3,4,3,3,3,3,4,3,9,3,3,3,2,3,3,2,3,18,2,2,3,3,3,3,2,3,9,2,6,3,2,2,3,4,2,9,2,3,3,4,2,3,3,3,9,4,2,6,2,3,6,2,2,9,3,2,3,2,3,3,4,2,9,4,3,3,3,3,3,5,2,9,4,2,3,2,3,3,2,2,9,3,3,6,3,3,3,3,3,9,3,2,3,3,4,3,3,2,9,2,2,3,2,2,3,4,2,9,2,3,6,3,4,3,2,3,18,3,4,3,3,3,3,3,3,9,3,2,3,3,3,3,3,3,9,3,2,3,2,2,3,2,3,9,3,3,3,2,2,6,2,5,9,3,3,3,3,3,3,3,2,18,3,3,3,2,3,3,3,3,9,2,2,3,2,2,3,2,2,9,2,2,6,3,2,3,2,3,9,2,3,6,5,2,3,2,3,9,2,3,3,3,2,3,4,2,9,3,2,3,2,2,3,3,3,18,2,2,3,3,2,3,2,2,9,3,2,3,2,3,3,2,3,9,5,2,3,4,2,3,3,3,9,3,3,3,2,3,6,3,3,9,2,3,3,3,3,3,2,2,9,3,4,3,4,2,3,2,2,9,4,3,3,2,5,3,2,3,9,2,3,6,2,2,3,3,2,9,2,4,3,2,4,3,3,2,9,2,2,3,2,3,3,2,3,9,3,2,3,2,3,3,4,2,18,5,2,3,2,2,3,3,2,9,2,4,3,3,3,3,2,3,9,3,3,3,4,7,3,2,2,9,3,3,3,2,2,6,4,4,9,3,2,3,3,2,6,3,4,9,3,3,3,4,2,3,3,2,9,4,2,3,2,3,3,3,3,9,3,2,6,2,3,3,3,2,9,2,3,3,2,6,3,3,3,9,2,5,3,2,3,6,4,3,9,3,3,3,3,3,6,2,2,18,3,2,3,3,3,3,2,2,9,3,4,3,2,4,6,2,2,9,2,3,3,4,3,3,5,3,9,3,2,3,3,3,6,3,2,9,3,3,3,3,3,3,2,4,9,2,2,3,3,3,6,3,2,9,4,2,3,2,3,3,2,3,9,3,2,6,3,3,6,4,2,9,3,3,3,3,2,3,2,3,9,2,3,3,3,2,3,4,3,9,2,5,3,4,2,3,2,3,18,2,3,3,2,3,3,3,5,9,3,4,3,2,3,3,2,3,9,2,2,3,4,2,3,2,2,9,2,3,3,2,3,6,2,2,9,2,3,3,3,3,3,2,4,9,3,2,3,5,2,6,2,4,9,2,3,3,3,3,3,3,2,9,9,3,6,2,2,3,2,3,9,2,4,3,3,4,3,3,3,9,3,2,3,3,3,3,2,3,9,2,3,3,3,2,3,3,3,18,2,3,3,2,2,3,3,2,9,3,4,3,3,3,3,2,3,9,2,3,3,4,2,3,3,3,9,2,3,3,3,5,6,3,3,9,3,3,3,2,3,3,2,4,9,3,2,3,2,2,3,2,2,9,4,3,3,3,2,3,3,2,9,2,3,6,2,2,3,3,2,9,6,3,3,3,2,3,2,2,9,3,2,3,3,2,3,2,4,9,4,2,3,3,3,3,3,3,18,3,4,3,2,3,3,3,2,9,2,4,3,3,3,6,2,4,9,3,2,3,2,3,3,3,3,9,3,2,3,2,2,6,4,2,9,3,2,3,2,3,3,2,4,9,3,3,3,3,3,3,2,3,9,2,5,6,2,3,3,3,2,9,3,4,12,3,3,6,2,2,9,3,3,3,2,4,6,3,2,9,3,2,3,2,3,3,6,2,9,3,3,3,4,2,3,5,3,18,2,2,3,3,2,9,3,2,9,2,4,3,3,4,3,3,2,9,2,2,3,4,2,3,3,3,9,4,4,3,3,3,6,3,3,9,3,2,6,3,2,3,3,4,9,2,2,3,3,3,3,2,3,9,4,3,3,2,2,3,3,2,27,2,2,6,3,3,3,2,3,9,3,3,3,3,4,3,3,5,9,2,3,6,3,3,3,4,2,9,2,3,6,2,2,3,3,3,18,3,3,3,2,3,3,2,3,9,3,4,3,4,2,3,4,2,9,3,3,6,6,2,3,3,3,9,3,2,3,2,2,6,2,2,9,2,3,3,2,2,3,2,4,9,2,2,3,3,2,3,2,3,9,4,2,3,3,3,3,4,2,9,2,3,12,2,3,3,4,2,9,4,3,3,3,2,3,2,2,9,2,3,3,3,4,3,2,3,9,3,2,3,3,3,3,2,2,18,2,3,3,3,5,3,2,2,9,2,2,3,3,2,3,2,3,9,3,3,3,4,3,3,3,2,9,3,3,3,3,2,6,3,2,9,3,3,3,5,3,3,3,2,9,5,7,3,3,3,3,2,4,9,2,3,3,2,3,6,2,3,18,2,2,6,2,3,3,3,3,9,3,3,3,3,4,3,2,3,9,3,2,3,3,3,6,2,2,9,2,2,3,2,3,3,3,3,18,2,2,3,3,4,3,2,3,9,3,4,3,2,2,3,3,2,9,3,3,3,4,3,3,3,2,9,2,5,3,3,2,6,2,2,9,2,2,3,3,2,3,3,4,9,3,3,3,4,2,3,2,2,9,4,2,3,2,3,3,2,6,9,2,2,6,3,2,3,5,2,9,2,3,3,3,2,3,2,2,9,3,3,3,2,3,3,2,3,9,3,3,3,3,3,3,2,2,18,2,4,6,3,2,3,4,4,9,4,4,6,4,2,3,3,2,9,3,3,3,4,3,3,2,2,9,3,2,3,2,3,6,3,2,9,3,2,6,3,4,3,4,4,9,3,2,3,3,2,3,2,5,9,2,2,3,2,3,3,2,3,9,2,3,6,4,3,3,2,3,9,2,3,3,3,2,3,3,3,9,2,3,3,2,2,3,8,3,9,3,4,3,5,2,3,3,3,18,4,3,3,2,3,3,3,3,9,2,4,3,3,5,3,3,3,9,2,3,3,2,2,3,3,2,9,2,3,3,3,3,6,2,2,9,2,2,3,3,2,3,2,4,9,3,2,3,3,2,3,3,3,9,4,2,3,2,4,3,2,3,9,3,3,6,2,2,6,2,2,9,2,3,6,3,6,3,3,4,9,2,3,3,2,3,3,4,2,9,2,2,3,3,3,3,3,3,18,2,2,3,2,2,3,2,2,9,3,4,6,2,3,3,2,3,9,5,3,3,4,2,3,3,2,9,2,4,3,3,2,6,3,4,9,3,3,3,2,2,3,3,2,9,3,2,3,2,3,3,4,3,9,2,3,3,2,3,6,3,2,9,3,2,6,2,3,3,2,4,9,3,3,3,4,2,3,3,2,9,3,7,3,3,3,3,4,3,9,2,2,3,2,3,3,2,3,18,2,5,6,2,2,3,3,2,9,3,4,3,2,3,3,2,3,9,3,4,3,2,2,3,2,3,9,2,2,9,3,4,6,3,3,9,3,2,3,2,2,3,5,4,9,2,3,3,2,3,3,3,3,9,4,3,3,3,3,3,3,2,9,3,2,6,3,3,3,2,3,9,6,2,3,2,2,3,2,2,9,3,2,6,3,2,12,4,2,9,3,2,3,3,3,3,3,3,18,2,2,3,2,3,3,3,3,9,3,6,6,3,3,3,3,2,9,2,2,3,2,3,3,2,5,9,3,2,3,2,2,6,3,2,9,3,2,3,3,2,6,2,4,9,2,3,3,3,4,3,3,2,9,4,2,3,2,2,3,2,2,9,3,3,6,5,3,3,3,3,9,3,3,6,3,4,3,3,3,9,2,3,3,3,3,3,4,2,9,4,3,3,2,3,3,3,2,18,2,2,3,3,3,3,3,2,9,2,4,3,2,3,3,2,4,9,3,3,3,4,3,6,2,3,9,2,3,3,3,2,6,3,2,9,3,3,3,3,2,3,3,4,9,2,3,3,2,5,3,3,2,9,2,2,3,3,2,3,3,3,9,2,3,6,3,3,3,2,7,9,3,2,3,4,4,3,2,2,9,3,2,3,2,2,6,2,2,9,5,2,3,3,3,6,6,3,18,3,3,3,2,3,3,2,3,9,3,4,3,2,3,3,3,2,9,2,2,3,2,3,3,3,3,9,3,3,3,3,3,6,2,3,9,2,3,3,3,2,3,2,4,9,3,2,3,3,3,6,3,2,9,4,2,3,2,2,3,5,3,9,3,3,6,2,3,3,2,4,27,2,5,3,3,2,3,4,3,9,3,3,3,2,3,3,2,2,9,2,3,3,3,3,3,3,3,18,2,2,3,3,3,3,3,2,9,3,2,3,3,3,3,5,2,9,3,3,3,4,3,3,3,3,9,3,2,3,4,3,6,3,4,9,2,3,3,2,3,3,2,4,9,3,3,3,3,4,3,2,3,9,2,2,6,3,3,3,2,3,9,2,2,6,3,2,3,2,3,9,3,3,3,2,4,3,2,2,18,3,3,3,3,3,3,4,3,9,3,3,3,3,2,3,2,5,18,4,3,3,3,2,3,2,2,9,2,4,3,7,2,3,3,3,9,4,3,3,6,2,3,2,3,9,3,2,3,2,2,6,2,3,9,2,3,6,5,3,3,2,4,9,3,3,3,2,3,3,3,3,9,4,3,3,2,3,3,3,2,9,3,2,6,3,2,3,3,3,9,4,2,3,2,4,3,3,3,9,3,4,3,3,3,3,4,3,9,3,4,3,2,2,3,2,2,18,2,2,3,2,2,3,2,2,9,2,4,3,2,3,3,2,3,9,2,3,3,2,5,6,3,2,9,3,2,3,3,2,6,3,5,9,3,3,3,2,3,3,2,2,9,2,3,3,2,3,3,2,2,9,4,3,3,3,3,6,3,2,9,5,3,12,2,2,3,4,3,9,3,2,3,3,4,3,4,3,9,2,2,3,4,3,3,2,3,9,3,3,3,2,2,3,3,2,18,2,3,3,2,2,6,3,3,9,2,4,6,2,3,3,2,2,9,3,3,3,2,3,3,3,2,9,3,3,3,2,3,6,3,2,9,3,3,3,4,3,3,2,4,9,3,5,3,3,4,3,3,3,9,2,2,3,3,2,3,3,3,9,2,3,6,3,3,3,3,3,9,2,2,3,2,4,3,2,3,9,3,3,6,3,3,6,6,2,9,2,3,3,3,2,3,2,3,18,2,3,3,2,3,3,2,2,9,3,4,3,2,4,3,2,2,9,2,2,3,4,3,3,2,3,9,3,2,6,2,3,6,3,3,9,2,2,3,2,2,3,2,4,9,2,3,3,3,4,3,2,2,9,4,2,3,3,2,3,3,3,9,3,2,6,3,2,3,3,5,9,2,2,3,2,2,3,3,3,9,2,2,3,2,2,6,4,4,9,2,2,3,2,3,3,2,3,18,3,3,3,3,3,3,3,3,18,4,2,3,5,3,3,3,2,9,3,3,3,4,3,3,3,2,9,2,3,3,2,3,6,5,2,9,2,2,3,2,3,3,3,4,9,3,3,6,2,2,3,3,2,9,2,3,3,4,2,3,4,3,9,3,2,6,2,2,3,3,3,9,2,2,3,3,4,3,3,2,9,2,3,3,3,3,3,4,4,9,4,3,3,3,7,6,2,3,18,3,3,3,3,3,3,2,3,9,2,2,3,3,3,3,3,3,9,3,2,3,2,2,3,3,3,9,3,3,3,3,2,6,2,4,9,5,2,3,3,3,3,3,2,9,3,3,3,3,2,3,3,2,9,4,2,3,2,2,6,3,2,9,2,3,6,3,4,6,2,3,9,3,3,3,3,4,6,2,4,9,6,3,3,2,3,3,2,3,9,2,3,6,3,2,3,2,2,18,2,3,3,3,2,3,2,2,9,3,2,3,2,2,3,2,2,9,3,6,3,4,2,3,4,2,9,2,2,3,2,2,6,3,3,9,3,2,3,3,3,3,2,4,9,3,2,3,4,3,3,2,3,9,4,2,3,3,2,3,5,3,9,3,3,6,3,3,3,3,2,9,2,3,3,2,4,3,3,3,9,5,2,3,3,3,3,4,2,9,2,2,3,3,4,3,3,3,18,2,2,6,3,3,3,3,2,9,3,4,3,3,3,6,3,4,9,2,3,3,4,3,3,3,3,9,3,4,3,3,3,6,2,2,9,7,3,3,3,2,3,3,6,9,3,3,3,2,3,3,3,2,9,2,4,3,3,3,3,2,2,9,3,4,6,3,2,3,3,4,9,3,3,3,2,2,3,3,3,9,2,3,3,5,3,3,4,2,9,2,2,3,3,3,3,4,2,18,3,3,3,2,3,3,3,3,9,3,4,3,2,2,3,3,2,9,3,3,3,2,2,3,3,3,9,2,3,6,2,3,6,3,2,9,3,2,3,2,2,3,2,6,9,2,2,3,3,2,6,4,3,9,4,3,3,2,3,3,2,2,9,3,3,6,3,5,3,2,2,9,2,2,3,3,4,3,3,2,27,3,3,3,2,2,3,4,2,9,3,3,3,2,3,3,3,2,36,3,1,3,2,3,3,2,3,9,5,4,3,2,3,3,2,3,9,3,2,3,2,2,3,2,2,9,3,3,3,2,3,6,2,4,9,2,2,3,3,3,3,3,4,9,2,2,3,2,2,6,2,2,9,2,10,3,3,3,3,2,3,9,3,2,6,2,4,3,3,3,9,3,3,3,2,4,9,3,3,9,2,3,3,4,2,3,4,3,9,2,5,3,2,3,3,2,2,18,3,4,3,2,2,3,3,2,9,3,4,3,2,3,3,2,3,9,3,3,3,4,2,3,2,3,9,2,3,3,3,2,6,5,3,9,3,3,3,3,2,6,3,4,9,2,2,6,3,3,6,2,3,9,4,3,3,3,3,3,3,3,9,2,2,6,3,3,3,3,2,9,2,2,6,3,2,3,3,2,9,3,2,3,2,2,3,2,3,9,2,3,3,3,3,3,3,3,18,2,2,3,2,2,3,3,2,9,2,2,3,2,3,3,3,5,9,3,2,3,4,2,3,4,3,9,4,2,3,3,3,6,3,3,9,2,3,3,2,2,3,3,2,9,2,3,3,2,3,3,2,3,9,2,3,3,5,2,3,3,2,9,3,2,6,3,3,3,3,3,9,2,3,3,3,4,3,2,6,9,2,3,3,3,2,3,4,2,9,2,3,3,2,2,3,2,4,18,3,2,3,3,3,6,3,4,9,3,4,3,2,3,3,3,2,9,2,7,3,2,3,3,2,2,9,3,2,12,3,2,6,2,3,9,3,2,3,3,5,3,2,4,9,2,2,3,2,3,3,3,2,9,6,3,3,2,2,3,2,3,9,3,2,6,2,3,3,2,3,9,3,3,3,2,2,3,3,3,9,5,3,3,2,2,6,4,2,9,2,3,3,2,3,3,2,2,18,3,2,3,3,3,3,2,2,9,2,4,3,2,3,3,2,2,9,4,3,3,4,3,6,2,2,9,2,2,3,3,2,6,3,3,9,3,2,3,3,3,3,3,4,9,4,2,3,3,3,3,2,2,9,2,2,3,2,3,3,2,3,9,3,5,6,6,3,3,3,2,9,3,3,3,4,4,3,3,3,9,3,3,3,3,1,3,2,3,9,3,3,3,2,2,3,3,3,18,2,2,3,3,3,3,5,4,9,4,4,3,3,3,3,2,2,9,2,4,3,2,2,3,2,3,9,2,3,3,4,2,6,2,3,9,2,2,3,2,3,3,3,4,9,2,4,6,3,2,3,3,2,9,4,2,6,3,2,3,7,3,9,3,3,6,2,2,3,3,3,9,3,2,3,3,4,3,3,2,9,2,3,3,2,2,3,4,5,9,3,2,6,3,3,3,3,4,18,2,3,3,5,3,3,3,2,9,2,4,6,3,2,3,2,3,9,2,2,3,4,4,6,3,3,9,3,3,3,5,2,6,2,3,9,3,2,3,2,3,3,2,4,9,3,3,3,2,2,3,3,2,9,2,2,3,2,3,3,2,3,9,2,3,6,4,2,3,2,2,9,3,2,3,2,4,3,3,3,9,2,3,3,3,2,3,2,2,9,3,2,3,2,4,3,3,2,18,2,3,3,2,3,3,4,2,9,3,4,3,2,6,3,3,3,9,3,3,3,4,2,3,2,3,9,3,3,3,3,3,6,2,3,9,3,2,3,2,4,3,3,4,9,3,2,3,3,3,3,2,2,9,6,3,6,2,3,3,2,2,9,3,2,6,3,3,3,3,3,9,3,2,3,3,2,3,3,2,9,3,3,3,3,4,3,2,3,9,3,3,3,2,3,6,3,2,18,3,3,9,6,3,3,2,3,9,2,4,3,3,2,6,4,2,9,2,2,3,4,3,3,3,2,9,2,3,3,3,3,6,4,3,9,3,5,3,3,3,3,3,4,9,2,3,3,3,2,3,3,3,9,2,3,3,2,2,3,3,3,9,3,3,6,2,2,3,3,3,9,3,3,3,2,10,3,5,2,9,2,2,3,2,3,3,4,3,9,2,3,3,3,2,3,2,2,18,2,2,3,3,3,3,2,2,9,2,2,3,3,2,3,3,2,18,3,3,6,4,3,3,2,3,9,3,2,3,3,3,6,3,3,9,2,3,3,2,2,3,2,4,9,6,2,3,3,2,3,3,3,9,4,3,3,3,4,3,2,5,9,3,2,6,3,2,3,3,2,9,2,3,3,3,4,3,2,3,9,3,3,3,2,3,3,4,3,27,2,2,3,2,3,3,2,3,18,3,2,3,5,3,3,4,2,9,2,4,3,2,2,3,3,3,9,3,4,3,4,2,3,3,4,9,3,2,3,2,2,6,3,2,9,2,2,3,3,3,3,3,8,9,2,3,3,3,3,3,2,3,9,4,2,3,3,2,3,3,2,9,3,3,6,2,2,3,2,2,9,2,2,3,2,2,3,3,3,9,3,3,3,3,5,6,4,2,9,3,3,3,3,3,3,2,2,18,2,2,3,2,2,6,3,2,9,4,4,3,2,2,3,3,3,9,3,3,3,4,3,3,3,3,9,5,3,3,3,3,6,2,2,9,2,2,3,3,2,3,2,4,9,2,2,6,4,3,12,2,3,9,4,2,3,2,3,6,3,2,9,3,2,6,3,3,6,3,3,9,2,2,3,3,6,3,2,3,9,3,4,3,4,3,3,2,2,9,2,2,3,3,3,3,2,2,18,3,2,3,3,3,3,2,2,9,4,6,3,3,3,3,2,3,9,2,3,3,2,2,6,2,2,9,2,3,3,3,2,6,2,2,9,2,2,3,2,3,3,3,4,9,2,2,3,4,2,3,6,3,9,2,4,6,3,2,6,2,3,9,2,4,6,3,3,3,2,4,9,3,2,3,3,6,3,3,3,9,3,2,3,7,2,3,2,3,9,2,3,6,2,3,3,3,3,18,3,3,3,2,2,3,3,3,9,2,2,3,2,2,3,3,2,9,2,2,3,4,3,3,2,4,9,2,2,3,2,2,6,3,5,9,3,3,3,3,2,3,3,4,9,3,3,3,3,3,3,3,3,9,4,2,3,3,3,3,3,3,9,3,3,6,3,3,3,3,4,9,3,3,3,5,2,3,3,2,9,3,3,3,2,4,6,4,2,9,2,2,3,2,2,3,2,2,18,2,3,3,3,4,3,3,3,9,3,4,3,3,2,3,3,5,9,3,3,3,2,2,3,5,2,9,4,2,3,3,3,6,2,2,9,3,3,3,2,2,3,3,2,9,2,3,3,2,2,3,3,5,9,4,3,3,3,5,3,2,3,9,2,3,6,3,3,3,3,3,9,3,2,3,3,4,6,2,3,9,3,3,3,3,3,3,4,3,9,2,2,3,2,3,3,2,3,18,5,2,3,2,4,6,3,2,9,3,4,3,2,3,3,2,3,9,3,2,3,4,2,3,3,4,9,3,2,6,3,2,6,3,3,9,2,2,3,3,2,6,3,2,9,3,2,3,3,3,3,4,2,9,4,3,3,3,2,3,2,3,9,3,3,6,3,3,3,3,3,9,3,3,3,3,2,3,2,3,9,3,5,6,2,2,3,6,2,9,4,2,3,2,2,3,3,3,18,3,3,3,3,3,3,2,3,9,2,4,3,3,3,3,3,3,9,2,2,3,2,2,3,5,6,9,2,2,3,3,4,6,3,2,9,2,2,3,3,3,3,3,2,9,2,3,3,3,2,3,3,2,9,4,3,3,2,3,3,3,3,9,4,2,6,11,2,3,2,2,9,3,3,3,3,2,3,2,3,9,2,2,3,3,2,3,2,3,9,2,3,3,2,3,3,4,5,18,3,3,6,2,3,3,3,5,9,3,4,3,2,2,3,3,2,9,3,2,3,2,2,3,2,3,9,3,2,3,2,2,6,4,2,9,2,3,3,3,2,3,3,4,9,2,3,3,5,3,3,2,3,9,2,2,3,2,2,3,3,3,9,2,3,6,3,7,3,3,3,9,4,3,3,2,4,6,2,2,9,3,2,3,3,2,3,2,3,9,3,2,3,3,2,3,2,3,18,3,2,6,3,2,3,3,2,9,2,4,3,3,4,3,2,3,9,3,2,3,4,3,6,3,2,9,3,3,3,3,5,6,3,3,18,2,2,3,2,2,3,2,4,9,3,4,3,3,3,3,2,3,9,4,3,3,3,3,3,2,3,9,3,3,6,3,2,3,2,2,9,5,2,3,3,4,3,2,3,9,3,2,3,3,3,3,4,3,9,3,2,3,2,2,3,2,2,18,3,2,3,4,3,3,3,3,9,3,4,3,3,2,6,3,3,9,2,3,6,4,3,3,3,3,9,3,3,3,3,3,6,4,3,9,3,4,6,3,2,3,3,4,9,2,3,3,2,2,3,2,3,9,2,5,3,2,2,3,2,3,9,2,2,6,3,3,3,3,3,18,2,3,3,3,2,3,2,3,9,2,4,3,3,3,3,2,2,9,2,3,3,4,3,3,5,2,27,3,2,3,3,4,3,2,2,9,7,4,6,3,2,3,2,3,9,3,3,3,2,3,3,3,2,9,3,2,3,3,3,6,2,3,9,3,3,6,2,3,3,3,2,9,2,2,3,3,3,3,3,3,9,4,3,3,3,3,3,3,3,9,3,3,6,3,4,3,3,2,9,2,3,3,3,4,3,4,5,9,2,3,3,2,2,3,4,3,9,2,2,3,3,2,3,3,3,18,4,3,3,3,2,3,3,3,9,2,2,3,2,2,3,2,2,9,2,3,6,6,3,3,3,3,9,2,2,3,2,2,6,3,2,9,2,2,3,3,2,12,4,2,9,3,2,3,3,3,3,2,3,9,2,3,3,3,2,3,2,2,9,3,3,6,3,3,3,3,3,9,3,3,3,2,4,3,3,3,9,3,3,3,2,3,3,4,3,9,3,2,3,2,2,3,2,2,18,4,3,3,2,5,3,4,2,9,3,4,3,2,3,3,4,2,9,3,3,3,4,4,3,2,3,9,3,2,3,3,3,6,2,2,9,3,3,3,2,3,3,3,4,9,5,3,3,2,2,9,2,2,9,4,3,3,3,2,3,3,3,9,2,2,6,3,3,3,3,2,9,2,2,3,3,4,3,2,3,9,3,2,3,3,2,6,2,4,9,3,2,3,3,3,3,2,3,18,2,3,6,3,2,3,3,3,9,2,4,3,3,3,3,2,2,9,3,2,3,4,2,3,2,3,9,2,5,3,3,3,6,3,3,9,2,3,3,2,3,3,3,4,9,4,2,3,2,2,3,3,5,9,4,4,3,2,2,3,2,5,9,3,2,6,2,2,6,5,2,9,3,2,3,3,2,3,2,3,9,4,3,3,3,2,3,4,3,9,3,2,3,2,2,3,3,2,18,2,3,3,3,2,3,2,3,9,3,6,6,3,3,3,3,3,9,3,3,3,4,3,3,3,2,9,2,3,3,2,3,6,2,2,9,4,3,3,3,3,3,3,2,9,2,3,6,3,3,3,3,5,9,4,3,3,2,2,3,4,4,9,2,3,6,2,3,3,3,3,9,2,3,3,2,2,3,3,3,9,3,4,3,3,3,3,4,3,9,3,7,3,6,2,3,3,3,18,3,3,3,2,3,3,2,2,9,3,4,3,3,3,3,3,3,9,2,5,3,4,3,3,2,3,9,2,2,3,3,3,6,3,3,9,2,3,3,3,2,6,3,4,9,3,3,3,2,4,3,3,3,9,2,2,3,2,3,3,3,3,9,3,3,6,2,2,3,2,2,9,2,3,3,2,6,3,2,3,9,3,3,6,3,3,3,2,2,9,2,2,3,2,3,3,3,2,18,3,2,3,3,3,3,3,2,9,3,2,3,2,2,3,2,3,9,5,2,3,4,3,3,2,2,9,2,3,3,3,2,12,3,3,9,2,4,3,2,3,3,3,4,9,3,2,3,2,3,3,4,2,9,4,2,3,4,3,6,3,3,9,2,2,6,3,3,3,2,3,9,2,3,3,3,4,3,2,2,9,2,2,3,3,2,3,2,3,9,3,2,3,2,3,3,2,3,18,3,5,3,3,2,3,3,3,9,3,4,3,3,3,3,2,2,9,2,2,3,2,3,3,3,2,9,2,3,3,3,4,6,7,2,9,2,2,3,3,3,3,5,2,9,3,3,3,3,2,3,4,2,18,4,2,3,3,2,3,3,2,9,3,3,6,2,2,3,2,4,9,3,2,3,3,2,3,2,3,9,3,3,6,2,2,3,4,2,9,3,3,12,3,2,3,2,2,18,2,3,3,3,3,6,2,3,9,3,4,3,2,2,3,2,3,9,3,3,3,6,3,3,3,5,9,3,3,3,3,2,6,2,2,9,2,2,3,2,2,3,2,4,9,3,2,3,3,3,3,2,3,9,4,4,3,3,3,3,4,3,9,3,2,6,5,3,6,2,2,9,3,3,3,2,4,3,2,2,9,3,3,3,2,2,3,4,2,9,2,3,3,2,3,3,3,3,18,2,3,3,3,3,3,4,3,9,4,2,3,4,3,3,3,3,9,2,2,3,4,3,3,2,2,9,3,3,6,2,2,6,3,3,9,3,3,3,3,4,3,2,4,9,2,2,3,3,5,3,2,4,9,4,2,3,4,2,3,2,2,9,3,3,6,3,2,3,4,3,9,3,2,9,4,4,3,2,3,9,3,3,3,2,3,3,2,3,9,5,2,3,3,2,3,3,4,18,2,2,6,2,2,3,3,3,27,2,4,3,3,2,3,3,2,9,3,3,6,2,3,3,2,2,9,2,3,3,3,2,6,3,3,9,3,2,3,3,4,3,2,4,9,3,3,6,2,3,3,3,2,9,2,3,3,3,3,6,2,2,9,3,3,6,5,3,3,3,3,9,2,5,3,2,2,3,2,3,9,2,3,6,3,2,3,2,2,9,2,2,3,2,2,3,2,2,18,4,3,3,3,2,3,3,3,9,2,4,3,2,2,3,5,3,9,4,2,3,2,2,3,2,2,9,3,2,3,2,2,6,3,3,9,2,2,3,3,3,3,3,4,9,3,2,3,2,3,3,3,2,9,2,3,6,3,3,3,2,2,9,2,2,6,3,3,3,3,2,9,3,4,6,2,2,3,3,4,9,3,2,3,2,4,3,4,3,9,2,3,3,3,3,3,3,5,18,2,2,3,2,3,3,2,3,9,2,6,3,2,3,3,3,7,9,4,2,3,4,2,3,3,2,9,2,3,3,3,3,6,2,2,9,3,2,3,5,3,3,2,2,9,3,2,6,3,2,3,2,3,9,4,3,3,2,2,6,3,2,9,4,3,6,3,2,3,3,2,9,3,3,3,2,4,3,7,2,9,2,3,3,2,2,3,4,2,9,3,3,3,3,3,3,3,2,18,2,3,3,2,2,3,2,3,9,2,2,3,3,3,3,3,2,9,2,2,3,4,5,3,4,2,9,3,3,3,2,2,6,3,2,9,3,3,3,4,5,3,3,4,9,3,3,3,2,2,3,2,3,9,4,2,3,4,3,3,3,2,9,5,3,12,3,2,3,3,2,9,3,2,3,3,4,6,2,3,9,3,4,3,3,3,3,4,2,9,3,2,3,3,2,3,2,3,18,2,3,3,2,2,6,2,3,9,3,4,3,3,3,3,2,3,9,3,6,3,2,3,3,3,2,9,3,3,3,3,2,6,2,3,9,2,2,3,2,3,3,3,2,9,2,5,3,3,3,3,2,2,9,4,2,3,7,3,3,2,3,9,2,3,6,3,2,6,3,3,9,2,3,3,2,2,3,3,2,9,3,2,3,2,3,3,6,2,9,2,4,3,3,2,3,3,2,18,2,2,3,4,3,3,3,3,9,2,4,3,2,3,3,4,3,9,3,3,3,4,2,3,2,3,9,2,3,6,3,3,6,2,3,9,2,3,3,2,3,3,4,4,9,2,3,3,2,3,3,2,3,9,4,3,3,3,2,6,2,2,9,3,3,6,3,2,3,4,5,9,3,2,3,2,4,6,4,2,9,3,3,3,3,2,3,4,2,9,2,3,3,3,2,3,3,2,18,3,4,3,2,2,3,3,2,9,3,2,3,5,3,12,2,4,9,2,3,3,4,3,3,3,2,9,3,3,3,2,2,6,3,2,9,4,2,3,2,3,6,2,6,9,3,2,3,3,2,3,2,3,9,4,2,3,2,4,3,2,2,9,2,3,6,2,3,3,2,2,18,3,3,3,3,4,3,2,2,9,3,2,3,3,2,3,4,3,9,3,3,3,2,5,3,3,2,18,4,2,3,3,2,3,3,2,9,3,4,3,4,3,3,2,3,9,3,3,3,4,3,3,3,2,9,2,2,3,3,3,6,2,2,9,5,2,6,4,3,3,3,4,9,3,2,3,2,3,6,3,3,9,2,6,3,3,2,3,2,3,9,4,2,6,3,2,3,3,3,9,3,4,3,3,4,6,3,2,9,2,3,3,3,3,3,4,2,9,3,2,3,3,2,3,3,3,18,2,2,3,3,3,3,2,2,9,2,2,3,3,2,3,2,3,9,4,5,3,2,3,3,3,2,9,3,2,3,3,2,6,2,3,9,3,4,3,3,3,3,3,4,9,2,2,3,2,2,3,2,3,9,4,3,3,2,2,3,5,3,9,2,2,6,3,3,3,2,3,9,2,3,3,4,2,6,3,2,9,2,3,3,2,3,3,10,2,9,3,4,3,2,2,3,2,4,18,2,3,6,2,2,3,2,3,9,2,4,6,2,2,3,3,2,9,2,3,3,2,2,3,3,4,9,2,3,3,2,2,6,2,3,9,3,3,3,2,7,3,3,6,9,3,2,3,3,2,3,3,3,9,2,2,3,3,3,3,2,2,9,3,2,6,3,3,3,2,2,9,3,2,3,3,4,6,2,3,9,2,2,3,5,2,3,4,3,9,3,3,3,4,3,3,3,2,18,4,3,3,2,3,3,2,3,9,3,2,3,2,3,3,3,4,27,2,3,3,4,2,3,3,2,9,3,3,3,3,3,6,3,2,9,3,3,3,3,3,3,};

int main() {
	int n; cin >> n;
	while (n % 2 == 0) n /= 2;
	while (n % 5 == 0) n /= 5;
	cout << a[n];
}