#include <stdio.h>
#define NUM_MAX 100000
unsigned long prime_map[]={
0xa08a28ac,0x28208a20,0x2088288,0x800228a2,0x20a00a08,0x80282088,0x800800a2,0x8028228,
0xa20a082,0x22880020,0x28020800,0x88208082,0x2022020,0x8828028,0x8008a202,0x20880880,
0x20000a00,0xa082008,0x82820802,0x800a20,0x28208a,0x20080822,0x20808020,0x2208088,
0x20080022,0x28a00a00,0x8a200080,0x8a2000,0x808800,0x2082202,0x80820880,0x28220020,
0xa008280,0x800020a0,0x20208228,0x80000208,0x20080802,0x20020208,0x20a082,0xa0000802,
0x8a20a08,0x8280,0x20820000,0x800020,0x82288002,0x80082880,0x8228a00,0x8080080,
0x80822080,0x20008808,0x8282282,0x82000020,0x20000028,0xa00200a,0x82082020,0x28820000,
0x80080200,0x800080,0xa28820,0x2082002,0xa0002800,0x8200000,0x808a208,0x802802,
0x208020,0x8008028a,0xa20a0002,0x20200,0x88000008,0xa0002020,0x28000808,0x2208202,
0x200000a0,0x208828,0x8220a208,0x820800,0x8008220,0x2208,0x2000080,0x20a08808,
0x80080000,0x22020002,0x800200,0x8820808a,0x82880822,0x20200a00,0x2008002,0xa20a0,
0x8220008,0x80002208,0x20820080,0x8008020,0xa082200,0x2800000,0x20008808,0x8200202,
0x20880,0x28020,0x88000002,0x882002,0x20220208,0xa280000,0x80,0x8820828,
0x8008800a,0xa0002802,0x208000,0x2000200,0x28a2,0x20800808,0x8282280,0xa00800a0,
0x20800200,0x8208082,0x22800800,0x20220800,0x8208080,0x2820000,0x8220008,0x200a000,
0x802880,0x20220,0xa08a088,0x80000880,0x200000,0x828208a,0x20a0000,0x28008200,
0x80008008,0xa2000822,0x20000,0xa080200,0x200a00a0,0x8028028,0x202,0x200a0080,
0x200820,0x2002080,0x820000a0,0x8208,0x800200a,0x8a2,0x820028,0x8208080,
0xa0002000,0x820a08,0x80080082,0x220a0000,0x808000,0x82288000,0x80022002,0x20000000,
0x2002080,0x802080,0x20808228,0x8002280,0xa00a0882,0x8008000,0x82200008,0x82082800,
0x8000000,0x8088002,0x2002020,0x228800,0x82002000,0x20820002,0x200800,0x88,
0x80820820,0x20800a20,0x8000020a,0xa00008a0,0x8828008,0x8200000,0x802022,0x800000,
0xa288280,0x22080020,0x208020,0x20a200,0x80880000,0x20208200,0xa088008,0x2802822,
0x8200,0x80088,0x20000002,0x8800008,0x88202000,0x82080020,0x200a00,0x80280202,
0x20080080,0x8a00000,0x202208,0xa0820080,0x28008020,0x2082080,0x82820082,0x20200820,
0x8200000,0xa0000,0x8020220,0x2000000,0x2880002,0x220a08,0x8008080,0x20002000,
0x820028,0x8020a00a,0x22000,0x28000a00,0x80280,0x2022880,0xa08200,0x88080008,
0x20,0x8828028,0x2208082,0x80080820,0x20020008,0x80000080,0x2820020,0x808000,
0x2080200,0x20082880,0x208820,0x80000,0x2002802,0xa00028,0x200,0x2080002,
0x8000200,0x8220000a,0x20080802,0x28220208,0x82200280,0x8800a0,0x8800020,0x2200002,
0x880882,0x20008820,0xa200,0x22000,0x208200,0x8002002,0x200008a2,0x20808008,
0x800a002,0x2000000,0x20a00,0x8200080,0x22820020,0x8208020,0x80000,0x80080882,
0x28020000,0x82280,0x80022080,0x20800228,0x200,0x2020802,0x28,0x8800a088,
0x82000,0x200000,0x8a008202,0x20080000,0xa00020,0x288002,0x20800082,0x8220220,
0x8008208,0x2020822,0x8800,0x80280088,0xa00200a0,0x20800008,0x8000000,0x802022,
0xa08,0x288280,0x20a0020,0x808,0x208008,0x80022080,0x20200220,0x2088008,
0x2800820,0x20000200,0x8000200a,0xa2000880,0x8000020,0x8208002,0xa2802820,0x8a00000,
0x2080082,0x20020080,0x8808,0x80000,0xa0882002,0x20020800,0x200a000,0x2800002,
0x208820,0x88200280,0x2080800,0x8008220,0x8800800a,0x82000,0x20200a08,0x208000,
0x2800000,0xa00000,0x80282000,0x80882800,0x28200000,0x2088080,0x20022,0x8008,
0x88082088,0xa0020002,0x28020200,0x200082,0x80800002,0x28000000,0x8a200002,0x802000,
0x20028,0x8000000a,0x20000080,0x208220,0x8008088,0x80000882,0xa00008,0x82208,
0x20080002,0x8020,0x80208000,0x82820,0x20800a08,0xa000000,0x20002020,0x8020808,
0x80000,0xa00a0080,0x208800,0x800a200,0x2802000,0x20000228,0x2000,0x22080880,
0x808200,0x2208008,0x2800002,0x800200,0x80080082,0x882000,0x8008800,0x8000820a,
0xa0000080,0x8000000,0x2208,0x20022,0x20000200,0x280202,0x800800a0,0x0,
0x8200208a,0x82882020,0x8800000,0x82008000,0x20880020,0x820028,0x8200a,0x880,
0x20a20,0x280,0x822822,0x20208000,0xa,0x80820,0x28028008,0x2202080,
0x2002,0x8800208,0xa200000,0x22020080,0x220020,0x82000208,0x80820880,0x28008020,
0x2000208,0x2002082,0x20000828,0x80082082,0x82020000,0x20200,0x8200088,0x80802000,
0x20a00200,0x200200,0x22000000,0x8a08808,0x82002000,0x882080,0x28a00,0x2082200,
0x80,0x208820,0x88000082,0x82080880,0x8,0x200200a,0x80802,0x20020800,
0xa088002,0x800000,0xa00020,0x2208,0x20820802,0x8008020,0x80200,0x80020002,
0x20800200,0x8082000,0x20002,0x28828020,0xa00a002,0xa0800002,0x20200008,0x8080,
0x200a0,0x8a20008,0x208a000,0x2802,0x8800,0xa00a000,0x22000,0x800208,
0x800008a,0x80000000,0x20008220,0x80200002,0x2000,0xa08,0x80200200,0x8a0000,
0x820,0x280002,0x80880882,0x20028020,0x2008000,0x800080,0x20a08220,0x8000000a,
0x20000002,0x20008228,0x8002002,0x22000800,0x8220808,0x88088082,0x20002000,0x8008820,
0x80280008,0x20880,0x8020800,0x2002088,0x80,0x800220,0x202000,0x20080822,
0x8020008,0x200200a,0x82080020,0x8020000,0x88000202,0x28020a0,0x820808,0x8020000a,
0x80822002,0x200200,0x8088008,0x20820,0x800220,0x80200080,0xa0020080,0x820000,
0x8a002008,0x80882002,0x8,0xa288000,0x20820020,0x8208800,0x8202,0x80000,
0x20028220,0x88208,0x800002,0x800028,0x82,0xa2000002,0x8800228,0x80008082,
0x2800,0x28800000,0x82000002,0x220000a0,0x20800,0x80002000,0x20082000,0x20020a00,
0x8000000,0x80020822,0x20000028,0x2082,0x20080,0x20820208,0x88000000,0x2800800,
0x220a00,0x88280002,0x2000000,0x8800820,0x80000,0xa0800800,0x800,0x2088080,
0x820000a0,0x8208,0x8280008,0x20080002,0x20820228,0x200000,0x20080820,0x20008,
0x80008080,0x28800a0,0x808000,0x200,0x82800,0x20208220,0x8080,0x2022882,
0x800a00,0x88000208,0x20a0820,0x8020,0x8008,0xa0002822,0x8800200,0xa000000,
0xa0020,0x20800,0x280202,0xa0800002,0x8000,0x800a008,0x2000080,0xa08008,
0x8020a,0x220800a0,0x20000028,0x8a000000,0x20002802,0x20200,0x80288280,0x2000020,
0x808020,0x2208208,0x20022800,0x20028000,0x2000288,0x80020020,0x20000808,0x8002002,
0x22080882,0x20020000,0xa200080,0x2002800,0x8800000,0x2000002,0x2000,0x808020,
0x82002008,0x20800800,0x200020,0x82208,0x800000,0x200800,0x80080000,0xa2,
0x20008008,0x2000008,0x20800022,0x20000800,0x8282,0x20000,0x8200028,0xa000,
0x80082880,0x8020020,0x2000208,0x802020,0x20,0x88282000,0xa2000800,0x820228,
0x820a082,0x82002,0xa00800,0x82080082,0x2082000,0x0,0x2000,0x200a0082,
0x8008020,0x88280,0x2020002,0x820,0x820200a,0xa0000,0x808200,0xa002002,
0x22800820,0x20a00800,0x80088000,0x2000080,0x8220820,0x288002,0x822002,0x8000200,
0x2000280,0x80002020,0x200,0x8202088,0x200a2,0x8808220,0xa008000,0xa0000000,
0x28000008,0x80200200,0x800a0,0x820000,0x80080008,0x800002,0x200200,0x800a008,
0x822880,0x200028,0x280,0x2020000,0x808200,0x200008a,0x80080802,0xa00008,
0x8a280200,0x80,0x828,0x82002,0x20880002,0x8020820,0x8000288,0x80000820,
0x20200000,0x8,0x200008a2,0x8,0x8220808a,0x2000800,0x8000000,0x88288200,
0x20a2000,0x8a00000,0x80280202,0x22802,0x20028000,0x80200,0x80020020,0x20800a00,
0x8002080,0x22000880,0x8028000,0x2008088,0x800020,0x820200,0x2000200,0x20082080,
0xa08800,0x82088008,0xa0002800,0x220800,0x800a208,0x22000,0x200000,0x80080080,
0x800808a2,0x8,0x80002080,0x20802002,0x200,0x208202,0xa0020,0x8020,
0x20a008,0x2880,0x28200000,0x808a000,0x802000,0x20200a08,0x80280082,0x82020000,
0x8800008,0x2,0x20802820,0x8200000,0x82000200,0x200a0000,0x8020000,0x80282208,
0x808a2002,0x8008200,0x8002000,0x80800080,0x20200020,0x800020a,0x80000,0x28008020,
0x82008002,0x20000820,0xa00,0x2000080,0x800080,0x20008,0x200200,0x200a0800,
0x20008a20,0x2088200,0x22880,0x20a08000,0x280,0xa0000080,0x20820208,0x2002000,
0x2880820,0x20020000,0x8208082,0x20020a0,0x200000,0x2002208,0x20880082,0x20020800,
0x8082080,0x2022882,0x800220,0x280200,0x80000820,0x8808020,0x2000000,0x20000000,
0x20200,0x8280080,0x20800080,0x8800028,0x2200000,0x20080002,0x208020,0x8000088,
0x20000,0x808008,0x80080000,0x2080820,0x20000020,0x88002000,0x82002000,0x200200,
0x8088200,0x2002000,0x8a00800,0x2008000,0x200a0880,0x200000,0x2280,0x80020002,
0x20800200,0x8000082,0x800a0802,0x20,0x88202008,0x2020,0x28a00000,0x88000200,
0x20802020,0x8000,0x8000800a,0xa0822080,0x0,0x80000,0x2000022,0x208a00,
0x20020a,0x2000882,0x20008208,0x200080,0x80082020,0x808,0x8000282,0x2820000,
0x20800,0x82008002,0x80882800,0x20020000,0x8a000,0x2002022,0x20,0x88080008,
0x20000082,0x8020200,0x8002082,0x20080002,0x8a00a00,0x2200000,0x22020,0x200808,
0x82080008,0x80820080,0x8020020,0x2008000,0x20022,0x20000800,0x80002002,0x20,
0x820208,0x8a002000,0x22802820,0x20a08,0x82000080,0x20020000,0x820020,0x8000a002,
0x802802,0x8200,0x8288,0x20820,0x800208,0x8280008,0x80080022,0x800028,
0x80,0x20800800,0x800,0x8200280,0xa2080,0x8,0x202,0x82,
0x28020,0x2002088,0x82800002,0x200000,0x80280280,0xa0000000,0x8000000,0x80008002,
0x2000020,0x220a00,0x8a200000,0x208800a0,0x8828008,0x88202,0x880,0x20200800,
0xa000,0x820208a0,0x20008000,0x88080002,0x2080000,0x820020,0x800a00a,0x800000,
0xa00008,0x8080200,0x20,0x8a00000,0x80280202,0xa0000000,0x0,0xa080208,
0x80822000,0x20008000,0x82000,0x22000022,0x28008028,0x88208008,0x882800,0x20a20208,
0x82008000,0x2080080,0x828000,0x2200008,0x22080,0x8000820,0x8088,0x82002020,
0x200020,0x80002,0xa2020000,0x208,0x200088,0x2000,0x8020a08,0x8208002,
0x2820080,0x8008020,0x200008,0x80820080,0x8208000,0x80008,0x2802880,0x20208008,
0x2008,0x20000802,0x8800000,0x80000002,0x80082022,0x20000800,0x80000202,0x800a0,
0x8200000,0x82002000,0x20000002,0x8000800,0x8002200,0x2820880,0x20000000,0x8000082,
0x80000080,0x28000020,0x80002000,0x800800,0x20820a00,0xa200082,0x2020000,0x8200820,
0x8008,0xa0082002,0x200000,0x88208,0x80000820,0xa00000,0x88000008,0x20000,
0x28000028,0x202002,0xa2000802,0x20000,0x2,0x2082080,0x208020,0x2088202,
0x80,0x20200820,0x2080000,0x2802002,0xa00828,0x80002002,0x22080000,0x8000020,
0x82,0x82000820,0x20800800,0x80280,0xa0000,0x828808,0x220a200,0x80880000,
0x8228020,0x2088,0x82800800,0x20000220,0x88080000,0x22,0x0,0x2202000,
0x22800002,0x8a00800,0x80208000,0x820000,0x8000800,0x88202,0x80080,0x20028a00,
0xa000080,0x820000,0x200,0x80280,0x80802,0x8,0x8200000,0x802020,
0x28000208,0x8a080000,0x2082020,0xa00008,0x8000a000,0xa0802000,0x200800,0x8002200,
0x22,0x208a00,0x20008a,0x220a0882,0x28020000,0xa002080,0x80080000,0x8820800,
0x2280000,0x220a0000,0x8000808,0x200200a,0x2080,0x208000,0xa208,0x2000,
0x20208808,0x8000000a,0x882,0x800020,0x20a000,0x20002820,0x8800a00,0x80200082,
0x22002020,0x8028000,0x82080008,0xa0000000,0x28000200,0x8088080,0x80000080,0x0,
0x80200280,0x800a0020,0x8228,0x8008002,0x80022,0x20220000,0x80208080,0x22020000,
0x8000800,0x80282202,0x208a2002,0x8220,0x8000,0x2020080,0x20a00800,0x80002280,
0xa0020,0x8000028,0x8082,0x800022,0x220808,0x8200,0x2000,0x828008,
0x2200,0x0,0x20028800,0x800a008,0x80,0x800228,0x8282000,0xa2000802,
0x808200,0x82008002,0x2002,0x20200008,0x2000080,0x8800a0,0x828028,0x208200,
0xa0800000,0x208800,0xa000080,0x80820800,0x8020,0x8080202,0x200008a0,0x800000,
0x8a000008,0x20800002,0x20008,0x8000082,0xa0020,0x20,0x88000,0x20082800,
0x8020a00,0x2002088,0x822020,0x8,0x8200002,0x2080000,0x8028008,0x88208000,
0x2000800,0x200008,0x88008202,0x2802000,0x20,0x280008,0x822882,0x220000,
0x82280,0x2,0x20800000,0x0,0xa0000,0x8008208,0xa200000,0xa0800002,
0x20800800,0xa000080,0x20080080,0x8008000,0x82008202,0x22880,0x20000020,0x80208,
0x2802,0x800208,0x88000002,0x2020000,0x8020020,0x202080,0x82080820,0xa00000,
0x80200002,0x20,0x20000,0x82280208,0x22000,0x20028800,0x8088080,0x80800880,
0x20200000,0x80002008,0x2080820,0x20220,0x82002008,0x2882800,0x200200,0x2008002,
0x802080,0x8820028,0x8800a,0x82000,0x28200820,0x2008000,0x80000022,0x20000200,
0x80008,0x20080080,0x28020,0x8000082,0x22000020,0x28000000,0xa000202,0x20a2000,
0x200008,0x8002,0x800082,0x20220800,0x2002088,0x82002802,0xa00828,0x80080,
0x82020802,0x28000000,0x200008,0x80000,0xa00000,0x280080,0x20800080,0x808020,
0x80202,0x80000000,0x8820,0x8002288,0x80800000,0x200020,0x8,0x82,
0x800220,0x2202082,0xa0800800,0x200000,0x88008202,0x22822000,0x8000,0x2000208,
0x80000000,0x28228000,0x0,0x20,0x20008000,0x282,0xa0802,0x28008020,
0x20a000,0x2880820,0x28020208,0x80008000,0x80080,0x820020,0x2082008,0x800800,
0x200a20,0x8008200,0x20002,0x8800,0x8a,0x82020080,0x20008208,0xa200008,
0x80802000,0x28020200,0x80282,0x20000000,0x8220020,0x8000a000,0x802880,0x8020020,
0x8088000,0x20,0xa08800,0x80200002,0x20020800,0x800000,0x8088,0x80880800,
0x20800000,0x208080,0x2020020,0x808008,0x80282000,0x20820082,0x20008820,0x2000000,
0x20002,0x208808,0x80002200,0x800000a0,0x20800000,0x88008008,0x2800002,0x20020208,
0x200002,0x20022080,0x8200000,0x2,0x80800000,0x220,0x8,0x22880,
0x800800,0x8082088,0x800a0080,0x8000,0x208082,0xa0080002,0x0,0xa200000,
0x20,0x8808008,0x80008,0x20882002,0x228200,0x88008,0x80000082,0x200820,
0x2002,0x82080002,0x8808000,0x2200002,0x22000000,0x20a00800,0x8a000200,0x200a0020,
0x8028820,0x208200,0x80002,0x20200000,0x2080,0x802820,0x28,0x8002008,
0x80080,0x28208,0x2088,0x22000800,0x8220a08,0x8088200,0x820020,0x800000,
0x80000202,0x20802,0x220200,0xa080000,0x80800080,0x808220,0x8200080,0xa00200a2,
0x20008000,0x800008a,0x2802000,0x200208,0x8080000,0x2002000,0x220828,0x8008a002,
0x20000,0x8200a00,0x8080008,0x802002,0x20800820,0x288,0xa2080822,0x8800208,
0x2008,0x20000020,0x20020a00,0x80000,0x20a0000,0x8200800,0x8020a202,0x80820080,
0x208000,0x2208,0x2802020,0x8820,0x280000,0x82020800,0x820200,0x8002008,
0x20000820,0x8800a00,0x80200000,0x20002000,0x808000,0x200200,0x800082,0x20000020,
0x8080080,0x2820000,0x8,0x80000000,0x808a0,0x8020008,0x82000002,0x20000800,
0xa00000,0xa200000,0x22802080,0x20800,0x20200a,0x80000800,0x220,0x8200,
0x20228a2,0x0,0x8002000,0xa0000,0x20000200,0xa008080,0x20880022,0x28220000,
0x8200200,0x2800080,0x8808020,0x8000000a,0x20080800,0x20008a00,0x2000000,0x2822882,
0x20,0x80000000,0xa0080020,0x20,0x2,0x22,0x8220808,0x82280080,
0x80020,0x808,0x200a200,0x20882,0x28008800,0x2000080,0x20020,0x20200228,
0x80200,0x80880,0x20808008,0x80202000,0x82000800,0x8800808,0x208000,0x20000000,
0x8200020,0x80000000,0xa0882,0x28000200,0x2080,0x80020000,0x8800,0x8002202,
0xa20200a0,0x20000,0x8002002,0x82080020,0x0,0x82080200,0x20080000,0x220020,
0x80280002,0x80002000,0x8000200,0x8002208,0x802,0x20800200,0x80088,0xa2000000,
0x20020208,0x80002080,0x20,0x20800000,0x8080082,0x20,0x820,0x200200a,
0x882800,0x20200000,0x8000208,0x8008a0,0x20200800,0x80200000,0x20000082,0x800028,
0xa002,0x80002000,0x800,0x2088280,0x2002080,0x8008808,0x80200000,0xa0002080,
0x8000200,0x2088200,0x82800080,0x8008,0x88000088,0xa0020,0x8800000,0xa00a,
0x20082020,0x200200,0x200080,0x2000,0x220000,0x200,0xa0802,0x208000,
0x2088080,0x2002882,0x200000,0x200080,0x80020,0x20808020,0x202082,0x2800800,
0x28200008,0xa008000,0x20080,0x8,0x2082208,0x802082,0x20020800,0x2008080,
0x802080,0xa20,0x80280002,0xa2000022,0x0,0x8020800a,0x20000802,0x20020008,
0x80000200,0x20002080,0x8008808,0x2202,0x20820000,0x20000,0x8008200,0x2802000,
0x20000008,0x8080008,0x20000022,0x808000,0x2008008,0x2800800,0x220000,0x80080002,
0x22802000,0x200000,0x82008002,0x20882,0x28208800,0x8080000,0x22000,0x8808,
0x200280,0xa2,0x28000000,0x82208000,0x80082800,0xa20200,0xa008000,0x20800a0,
0x800,0x2080000,0xa0002000,0x8020800,0x82280,0x2002002,0x20208000,0x8000a,
0x20a0020,0x8828200,0x80,0xa0002020,0x8020000,0x8280000,0x2880000,0x28000,
0x220020a,0x880800,0x8000220,0xa080000,0x802802,0x20000000,0x8002008,0x80000082,
0x20028,0x80008002,0x20082800,0x28800000,0x80088200,0x20080080,0x208000,0x80000008,
0x8a0082,0x20,0x8280,0x800200a0,0x20200028,0x80202080,0xa0880,0x8208,
0x80000002,0x882000,0xa00000,0x88002,0x22020080,0x8800020,0x88200,0x820800,
0x28000200,0x0,0x80020082,0xa08800,0x88200000,0x82,0x8800008,0x8008000,
0x80000,0x200008,0x2208002,0x20,0x820020,0x2080202,0x20002800,0x20800,
0xa002080,0x2022000,0x800000,0x80280088,0x0,0x28000020,0x208002,0xa2000002,
0x20020008,0x82000280,0x880000,0x800,0x28a002,0x800002,0x28208000,0x200a088,
0x82820020,0x20808000,0x80080002,0x22000800,0x20808200,0x80208000,0x82000800,0x808,
0x282,0x2800020,0x8200800,0x80280200,0xa0082000,0x8200000,0x2000208,0x2020,
0x800228,0x8200200,0x2080000,0x20028,0x82000080,0x2080000,0x20a20008,0x80000200,
0x22002000,0x808,0x200200a,0x2,0x8020a00,0x88,0x20000,0x220,
0x80200200,0xa0020020,0x8820200,0x88,0x80880002,0x8000000,0x2080002,0x208200a0,
0x200800,0x8002,0x22080,0x28000020,0x2088000,0x8000a0,0x20800200,0x202088,
0x2000880,0x8800000,0x80202000,0x22002022,0x28000200,0x280200,0x22020,0x828000,
0x80280000,0x20080002,0x8800,0x8200,0x82000022,0x20000808,0x2002,0x80000080,
0x800008,0xa000,0x22800002,0x20820a00,0x2200082,0x20020000,0xa00008,0x80000008,
0x80822000,0x8200000,0x2000080,0x82000022,0x20000a08,0x80080088,0x80,0x28020208,
0x200000,0x802,0x200808,0x8200200,0x880080,0x20020,0x200,0x20000800,
0x208020,0x8088080,0x82000800,0x208,0x28220a,0x20820,0x20000020,0x220008a,
0x80082800,0xa20008,0x82000200,0x8000a0,0x820800,0x2200000,0x80000082,0x8208000,
0x8008,0x22000,0x20200008,0x8000002,0x200000a0,0x20008020,0x2000088,0x2002,
0x220a00,0x80000082,0x802020,0x8000800,0x8,0x200a2082,0x8020800,0x8000000,
0x20000,0x808a28,0x202000,0x80080,0x28000,0x80002002,0x802000,0x8200200,
0x8000000,0x2080020,0x828028,0x208a000,0x80020802,0x200220,0x80000,0x80820800,
0x20208a20,0x80000208,0xa2020000,0x28820000,0x80002000,0x20080000,0x208,0x200280,
0x20820000,0x8020028,0x200008,0x80880,0x28020,0x200a000,0x2880,0x800800,
0x2000,0x82020080,0x20200,0x8208002,0xa2080020,0x20a00200,0x80288080,0x2000000,
0xa08000,0x2200008,0x80880000,0x20008200,0x8000280,0x80000802,0x8820,0x8202280,
0x2000800,0x28000200,0xa00a002,0x20802002,0x20800008,0x82,0x822000,0x220008,
0x80080202,0x20880800,0x8200800,0x80280,0x20000a0,0xa00808,0x200088,0xa0000,
0x20800028,0x202080,0x80020,0x8020000,0x80208000,0x2800000,0xa00000,0x2080008,
0x2,0x220220,0x2008008,0x80822002,0x800208,0x88202000,0x20802,0x20808020,
0x2000008,0x20002800,0x8800008,0x2200000,0x20000080,0x8008800,0x2082202,0xa0080000,
0x20000,0xa000288,0x80822000,0x20a00208,0x80000008,0x0,0x20220,0x88000002,
0x2800802,0x8020808,0x280280,0x22000,0x8000,0x208200,0x82080,0x200a00,
0x80,0x80800022,0x800820,0x202080,0x80820,0x28,0x8000,0x0,
0x28220200,0x82000202,0x880000,0x208008,0x20a00a,0x20802800,0x200820,0x88208,
0x80802020,0x20008000,0x280280,0x80000882,0x20200,0x0,0xa0802020,0x8020200,
0xa008082,0x208a0000,0x28800,0x2200200,0x80000,0x20008220,0x8000000,0x2822,
0xa08808,0x8082000,0x80020800,0x8000208,0x208008,0x2000002,0x800000,0x8080,
0x2020000,0x208000,0x80002008,0x20022000,0x220,0xa082000,0x800008a0,0x200820,
0x282,0x82020000,0x8000000,0x800a,0x20000022,0x820800,0x80200002,0x20002000,
0x8000800,0x202,0x20022000,0x8008200,0x0,0x82002000,0x20808208,0x280280,
0x80020080,0x20808000,0xa200002,0x2000820,0x200800,0x8000000,0x2800020,0x8a20028,
0x2008200,0x2,0x8200,0x8080088,0x2,0x808,0x80200202,0x20002,
0x8000000,0x8080,0x2020,0x20808,0x88280000,0x82000,0x8000028,0x202,
0xa0800002,0x208800,0x8088,0x2820880,0x8000,0x88002208,0x2080820,0x820208,
0x8200080,0x20800002,0x200000,0x8200000,0x82000,0x808020,0x200000,0x20002080,
0x28008200,0x8080088,0x80800002,0x800220,0x80002,0xa20a0080,0x8000000,0x8200a000,
0x2000820,0x0,0x8a000002,0x880080,0x8800,0x8000,0x820002,0x8000000,
0x82208,0x822,0x200820,0x80200008,0x2000820,0x20008208,0x88000008,0x2000,
0x800808,0x200202,0x20080,0x808,0x2202008,0x820000,0x8028200,0xa000000,
0x28a0,0xa00000,0x8080000,0x82000082,0x8800200,0x2000,0xa0000800,0x800,
0x8200,0x22000,0x228008,0x2080208,0xa0020082,0x28020020,0x88000,0x80020880,
0x820,0x202082,0x2000080,0x8828028,0x80002002,0x880802,0x20820a00,0x82008080,
0x20020000,0x8820020,0x80008002,0x822002,0x20000000,0x2000208,0x2000,0x20000200,
0x82080,0x80000022,0x8020008,0x8002000,0x22800000,0x28000800,0x82000000,0x2080,
0x8808000,0x8000a000,0x2080,0x20200000,0x88000,0x820000,0x28,0x80208,
0x2,0x800200,0x200800a,0x2082022,0x8a00000,0x200080,0x2020,0x8000800,
0x200a000,0x20800,0x220000,0x800a080,0x82800020,0x800200,0x200,0x80820,
0x20000228,0x8080,0x80802802,0x8200208,0x88288000,0x20080000,0x800000,0x280200,
0x20002080,0x8800,0x8002200,0x80020020,0x20008820,0x280,0x2000080,0x28000,
0x820808a,0x80082800,0x20020200,0x2088002,0x802000,0xa20828,0xa,0x20020002,
0x20000,0x808a088,0x2000800,0x800,0x80000282,0xa0000820,0x200,0x82202000,
0x880000,0x28800208,0x2000000,0x22020000,0x8008,0x80002000,0x80000000,0x20200000,
0x0,0x2800882,0x8220,0x80002008,0x82020000,0x8000008,0x8002008,0x2002022,
0x8000a00,0x2000202,0x20080020,0x8000000,0x2002200,0xa0082002,0x800,0x2002080,
0x2000020,0x20008028,0x208,0x80080880,0x20008028,0x8000002,0x2002000,0x220208,
0x80000082,0x2020000,0x220028,0x282002,0x800a2800,0x20008000,0x2000280,0x800,
0x208800,0x80000200,0x200a0080,0x20800228,0x2200000,0x800822,0x8020808,0xa008080,
0x820020,0x8008,0x80000008,0x20080000,0x20200800,0x8a080,0x82002082,0x200800,
0x8002008,0x20080800,0x28800000,0x82200088,0x2080800,0x800000,0x8200200,0x800080,
0x28008,0x82000,0x802,0x8228000,0x8008,0x2800020,0x800000,0x80000200,
0x80000,0x8020,0x88200000,0x22000002,0x8200a08,0x88080200,0x800000,0x200020,
0x82000008,0x20080000,0x8008800,0x2000280,0x80002082,0x800208,0x282000,0x80000000,
0x8028000,0x8020208a,0x80000,0x8,0x8080202,0xa0,0x20820,0x80200000,
0xa0800080,0x800,0x82280,0x80820020,0x8a00,0x0,0x22000022,0x8000000,
0xa002088,0x80880000,0x8820000,0xa280202,0x0,0x200008,0x2000000,0x800000,
0x20200000,0x8002000,0x2002,0xa00,0x8008a,0x20020000,0x800228,0x20000a,
0x800800,0x200a00,0x80,0x20a2080,0x800008,0x80082008,0x80080000,0x28000a20,
0x82000,0x828000a2,0x20208000,0x80000202,0x2020000,0x820220,0x8000,0x2002820,
0x20800000,0xa080080,0x2820000,0x820,0x200202,0x20802800,0x28008000,0x8008,
0x80000882,0x20200000,0x200,0x80020002,0x200,0xa000080,0xa0080022,0x200800,
0x2000282,0x20020a0,0xa08028,0x80008008,0x20080000,0x20200,0x2008000,0x82020880,
0x800008,0x200,0xa2020022,0x20800000,0x80200000,0x82082822,0x28000008,0x8280080,
0x20082020,0x8828000,0x8000,0xa0020080,0x20800,0x2200,0x80020000,0x808000,
0x88082000,0x20000082,0x20000,0x80002002,0x20002002,0x8200208,0x8008280,0x20002020,
0x8000820,0x82088008,0x80080000,0x208800,0xa002200,0x20a0,0x800,0x2282,
0xa0080000,0x28000028,0x8020a000,0x2080000,0x220000,0x88008002,0x0,0x8020,
0x282000,0x822002,0x200000,0x8088,0x2,0x8220,0x80200288,0x20020082,
0x20808008,0x88000008,0x20000000,0x820000,0x8000000,0x220800a0,0x8008820,0x82200208,
0x22000,0x8220020,0x8a000,0x8000a0,0x8,0x202082,0x20000000,0x20,
0x8200000,0x20000800,0x20800800,0x88000,0x20a0080,0x808,0x2002200,0x80082000,
0x820,0x2082000,0x2020800,0x20208008,0x2280,0x80820,0x20028200,0x82002008,
0x20800000,0x800800,0x88000000,0x2800000,0x8200808,0x80200,0x80880000,0x200200,
0x8000,0x80000822,0x20800008,0x282000,0x80080000,0x828020,0xa202002,0x800802,
0x20000,0x2208080,0x82080,0x8220000,0xa200,0x82800,0x220200,0x2000080,
0x82002800,0x800008,0x8002082,0x800a0020,0x20000000,0x80000000,0xa2080800,0x8000a00,
0x8080280,0x2000,0x8008820,0x2202200,0x820880,0x20220800,0x8000,0x0,
0x20200228,0x2,0x880,0x20000020,0x82002000,0x2002002,0x8820a00,0x200080,
0x2002020,0x8000800,0x2080202,0xa0020080,0x8a00,0x2080,0x800000,0x808000,
0x282082,0x82080022,0x8000000,0x200200a,0x80000820,0x28800208,0x80080200,0x20800000,
0x220820,0x2002000,0x20002000,0x800,0x8000200,0x80000022,0x20a08800,0x8000000a,
0x80,0x8028000,0x8000088,0xa0080002,0x8,0x208000,0x22080080,0x8000028,
0x8002,0x802000,0x8028000,0x80008,0x20000a0,0x808000,0x88002082,0xa2000080,
0x20000,0x88200008,0x800000,0x8000a00,0x2000082,0x20002000,0x220000,0x2208,
0xa0080002,0x8020,0x80280,0x820800,0x208000,0x8000000a,0x82000800,0x820020,
0x2002000,0x2020,0x220000,0x88002,0x20020080,0x8a00000,0x8028a002,0x800,
0x8000820,0x2008088,0x82,0x800a00,0x80000080,0xa00a0,0x820220,0x820a080,
0x880022,0x220800,0x8008200,0x2820000,0x8828008,0x88008,0x802002,0x200220,
0x2008000,0x880,0x820,0x80002200,0x82020000,0x808000,0x2008002,0x80000802,
0x200000,0xa000200,0x20882000,0x8028008,0x2200000,0x80002,0x20000820,0x2088,
0x80000820,0x0,0x8000002,0xa0,0x808008,0x20a002,0x2002800,0x820a00,
0x80008002,0x22080000,0x0,0x2080208,0x20002,0x28000000,0x2082088,0x800080,
0x20000220,0x202280,0x20020080,0x0,0x200a,0x80800000,0x800008,0x80008000,
0x20000080,0x828808,0x2082000,0xa0000002,0x8000200,0x88200,0x802020,0x20200220,
0x80080,0x800800a2,0x8000208,0x2000000,0x20,0x20020800,0x8000280,0x22020020,
0x28820,0x200200,0xa2880,0x0,0x2002000,0x2000002,0x208228,0x820008a,
0xa0020002,0x8,0x80000088,0xa0080820,0x200000,0x80080,0x2080,0x8800,
0x2282000,0x80022080,0x20028000,0x8008280,0x80820080,0x20200000,0x8200200,0x20800,
0x800008,0x80002000,0x2800002,0xa00,0x2008002,0x802000,0x8800000,0x282008,
0xa0020800,0x20008a20,0x200,0x2002802,0x208a00,0x80080208,0x80020002,0x0,
0x820a002,0x2000022,0x20000008,0x8a200200,0x28a0080,0x8208000,0x80002200,0x800,
0x20200820,0x8a000,0x820080,0x0,0x808200a,0x80080000,0x28008220,0x2000000,
0x80002002,0x820000,0x0,0x20802020,0x8828800,0x2,0x20080800,0x28020,
0x2002088,0x800008a0,0x200200,0x2202,0x2000080,0x20808000,0x8002000,0x80002800,
0x820a00,0x288002,0x22880000,0xa08020,0x2080008,0x0,0x28020000,0x8080200,
0x80022080,0x20808a00,0x8200002,0x20000080,0x8,0x200a008,0x2080020,0x200000,
0x82000000,0x208800a0,0x808,0x8020000a,0x80000882,0x8220200,0x8000200,0x2,
0x800,0x28a,0x200008a0,0x28008208,0x80200000,0x0,0x800a08,0x8000002,
0x80000,0x8200020,0x8002,0x80880080,0x20220020,0x2000,0x2,0x200,
0x88280088,0x2000802,0x228,0x8008,0x20002800,0x20800000,0x82008280,0x2082080,
0x208008,0x200,0x20000,0x8000a20,0x2002080,0x2800022,0x8020,0x200200,
0x20000a0,0x20020000,0x8002,0x2000020,0x20020008,0x80080002,0x20020080,0x8,
0x88002,0x20800,0x28208000,0x2000008,0x82000000,0x8208,0x80280008,0xa0080080,
0x808020,0x80,0xa2080800,0x28000000,0x2000000,0x8200a0,0x8208020,0x88202,
0x20880002,0x200a00,0x8080,0x2000,0xa00000,0x82200,0x22080002,0x8008200,
0x2008002,0x2080000,0x8000a00,0xa000000,0xa0,0x820000,0x80000,0x800a0082,
0x20020000,0x2002008,0x82000020,0x208028,0x8002002,0x80,0x20028200,0x88202080,
0x800,0x820000,0x280002,0x20a0000,0x20,0x80280008,0x20002880,0x8000,
0x8082200,0x2000,0x20000208,0x8280082,0x20000880,0x8000028,0x208080,0x800020,
0x200000,0xa000002,0x208820a0,0x0,0x208002,0x2800,0x0,0x8008080,
0x2802,0x20200000,0x80000008,0x82080022,0x8020000,0x2200088,0x80000002,0x20820208,
0x2288000,0x80080,0x228020,0x8020200a,0x802000,0x20200200,0x8002008,0x2020,
0x828,0x8082002,0x80,0x28,0x200000,0x80800022,0x800200,0x80088002,
0x20000000,0x8200000,0x202208,0x0,0x8028800,0x2008080,0x20020,0x20000028,
0x80000202,0x80000800,0x20028008,0xa000,0x82800,0xa00800,0x2280000,0x20022000,
0x8220008,0x80000200,0x800000,0x20008800,0x80208,0x2020000,0x20a00008,0x8280008,
0x800000a2,0x20000028,0xa00a080,0x80800002,0x220808,0x88000280,0x800080,0x8220000,
0x2000008,0x20002000,0x8220,0x8002080,0x2800080,0x800220,0x8008a,0x20,
0x20008020,0x200000,0x2,0x20200,0x80080000,0x22000,0x28,0x2002,
0xa0082,0x8000000,0x8002000,0x880,0xa08000,0x82000,0x802,0x8,
0x8000a000,0x2,0x8a20808,0x200,0x2020000,0x820,0x82200008,0xa2882,
0x20200800,0x80208,0x800082,0x800200,0x200,0x22020822,0x8020000,0x8800a002,
0x82082000,0x20008,0x2,0x22080020,0x208800,0x2202000,0x802000,0x20020,
0x8080000,0x820820,0x800220,0x80208,0x20080020,0x20828200,0x8a000000,0xa0800000,
0x8000808,0xa200002,0x20200a0,0x0,0x82000000,0x880080,0x28020020,0x2008200,
0x800,0x20200a08,0x80008,0x82000880,0x8820020,0x808a,0x2880820,0x8000200,
0x8200,0x20080020,0x8a08800,0x80080200,0x80800080,0x20200,0x200,0x820000,
0x20000828,0x8a,0xa0,0x20220,0x88008008,0x80022,0x800000,0xa000080,
0x820080,0xa00008,0x208200,0x20000800,0x0,0x80208,0x820200a0,0x8000,
0x88200080,0x80020,0x8000008,0x202002,0x2000802,0x0,0xa000280,0x2820000,
0x8828028,0x82008000,0x20000000,0x220820,0x8080000,0x2082,0x8,0x8202280,
0x80080022,0x20000200,0x8a,0x2000820,0x200200,0x82280000,0x80,0x808020,
0x2000000,0x80800800,0x200000,0x8002200,0x82000020,0x20008028,0x8000002,0x2,
0x20020,0x82208088,0x20000002,0x208,0x80202,0x82000,0x808800,0x2008000,
0x200a2000,0x28000800,0x8082208,0x2000,0x20800200,0x8002000,0xa2020822,0x20028008,
0x8008,0x80082800,0x8800200,0x0,0x2802080,0x20020,0x80088000,0xa0020082,
0x8200a00,0x82008,0x82020002,0xa00800,0x80200202,0xa2020000,0x20000008,0x82000008,
0xa0802000,0x8000000,0x202,0x20800000,0x8200008,0x2008202,0x80082800,0x8020000,
0x8008,0x2802000,0x8228,0x800008a,0x2020880,0x8000000,0x80000082,0x80800,
0x800000,0x82288280,0x2080000,0x8a20000,0x2000,0x20000082,0x20,0x80000,
0x8000a0,0x800,0x800000a,0xa0000,0x8000008,0x80008000,0x2802022,0x20220008,
0x88088000,0x2802000,0x20000,0x80008202,0xa0080000,0x220,0x2000280,0x82000000,
0x200800,0x202000,0x80002,0x8820028,0xa080,0xa0000800,0x8200000,0x80008282,
0x82000,0x20000,0x8008a00a,0x802002,0x20200820,0xa000000,0x80000000,0x200020,
0x8000088,0x22080000,0x8000220,0x82200088,0x2000002,0x8800200,0x200000,0x200a0,
0x8820000,0x82002,0x80800000,0x20228800,0x8000088,0x20080,0xa00200,0x80082008,
0x22000082,0x808208,0x80208000,0x800,0x800200,0x8200202,0xa0020,0x8808820,
0x80000,0x20080880,0x20020200,0x82000,0x22022,0x8,0x8200000,0x2080822,
0x20000008,0xa00a080,0x820,0x20020000,0x80202,0x2082080,0xa00800,0x280008,
0x22002,0x8200800,0x8000,0x2,0x20200200,0x280080,0xa0080080,0x200,
0x2002088,0x22,0x20a08,0x2000002,0x20000,0x8008008,0x80202208,0x22080,
0x8020,0x2200,0x2002820,0x0,0x88200008,0x82000000,0x8000000,0x820200a,
0xa0080802,0x8a00000,0x2088000,0x20000000,0x8800,0x82000008,0x20082000,0x20008a20,
0x8000,0x2020000,0x20008000,0x80000080,0x20a00a0,0x20000008,0x2008000,0x800,
0xa00008,0x8000,0x22800000,0x200828,0x208000,0x882002,0x28000000,0x80080,
0x2022800,0x8a08,0x2280,0xa0000,0x800200,0x8000,0x2,0x28020800,
0x200000,0x28a0020,0x8808028,0x80000000,0x800880,0x208200,0xa000008,0x82000002,
0x200,0x200002,0x80020800,0x0,0x80000008,0x82020,0x20020800,0xa000000,
0x8a2000,0x800,0x280202,0x20080880,0x8200800,0x8008208,0x800800,0x8020,
0x200a,0x20000020,0x28008,0x2080,0x22800002,0x20a00,0x8200000,0x2820000,
0x200000,0x2280002,0xa00a2080,0x8028000,0x80208,0x820020,0x8220,0x2002,
0x80020880,0x28008020,0x200a,0x802020,0x800000,0xa080202,0x2002000,0x200000,
0x280000,0x80020880,0x20220,0x8080,0x80002000,0x200,0x80000288,0x22080880,
0x8800000,0x8000080,0x80082000,0x28000200,0x200282,0x820000,0x20800,0x82208202,
0x80080000,0x20000220,0x2080008,0x2000000,0xa00008,
};
int main(void)
{
int n;
scanf("%d", &n);
if(n<2 || NUM_MAX<n)
{
printf("2 ~ %d までの数値を入力してください\n", NUM_MAX);
return 1;
}
if((prime_map[n/32]>>(n%32))&1) printf("%d は素数です\n", n);
else printf("%d は素数ではありません\n", n);
return 0;
}