#define R 500
#define C 500
#define NNZ 2399
const double val[2399] = {
  566,
  508,
  850,
  780,
  944,
  598,
  772,
  880,
  764,
  656,
  138,
  757,
  929,
  234,
  168,
  629,
  639,
  434,
  849,
  793,
  203,
  811,
  250,
  770,
  322,
  535,
  826,
  609,
  899,
  926,
  211,
  755,
  900,
  691,
  386,
  821,
  454,
  791,
  849,
  256,
  821,
  29,
  679,
  944,
  55,
  689,
  453,
  631,
  799,
  854,
  545,
  97,
  337,
  258,
  695,
  667,
  581,
  104,
  491,
  517,
  761,
  369,
  316,
  42,
  86,
  432,
  954,
  736,
  333,
  321,
  184,
  920,
  258,
  949,
  604,
  907,
  70,
  453,
  796,
  102,
  3,
  105,
  371,
  388,
  153,
  908,
  176,
  567,
  334,
  973,
  911,
  323,
  681,
  300,
  265,
  711,
  871,
  870,
  463,
  969,
  535,
  688,
  276,
  908,
  384,
  988,
  256,
  416,
  258,
  523,
  80,
  911,
  241,
  191,
  411,
  127,
  894,
  259,
  664,
  129,
  609,
  146,
  763,
  109,
  369,
  881,
  878,
  224,
  635,
  498,
  460,
  363,
  481,
  222,
  761,
  489,
  753,
  62,
  261,
  389,
  351,
  189,
  319,
  557,
  5,
  485,
  806,
  119,
  366,
  85,
  123,
  918,
  66,
  205,
  786,
  313,
  555,
  22,
  760,
  904,
  255,
  912,
  950,
  676,
  342,
  736,
  251,
  170,
  923,
  790,
  312,
  716,
  648,
  57,
  676,
  972,
  250,
  215,
  792,
  798,
  915,
  61,
  381,
  897,
  686,
  568,
  393,
  969,
  893,
  205,
  721,
  684,
  38,
  667,
  704,
  750,
  364,
  123,
  158,
  892,
  306,
  409,
  188,
  394,
  554,
  602,
  59,
  9,
  987,
  897,
  332,
  873,
  770,
  632,
  434,
  598,
  599,
  207,
  211,
  410,
  768,
  708,
  462,
  687,
  300,
  864,
  839,
  183,
  21,
  282,
  990,
  578,
  952,
  42,
  149,
  235,
  777,
  156,
  568,
  400,
  783,
  238,
  390,
  108,
  422,
  392,
  414,
  338,
  524,
  535,
  893,
  160,
  163,
  798,
  836,
  662,
  181,
  946,
  774,
  113,
  438,
  721,
  631,
  577,
  739,
  62,
  928,
  523,
  352,
  603,
  974,
  291,
  47,
  875,
  260,
  754,
  13,
  890,
  989,
  104,
  22,
  36,
  803,
  39,
  241,
  95,
  589,
  603,
  230,
  471,
  978,
  617,
  603,
  652,
  21,
  755,
  294,
  753,
  609,
  494,
  93,
  387,
  243,
  128,
  777,
  636,
  303,
  665,
  761,
  355,
  611,
  605,
  627,
  834,
  616,
  59,
  109,
  268,
  638,
  117,
  338,
  89,
  95,
  4,
  64,
  575,
  300,
  783,
  453,
  878,
  939,
  984,
  338,
  344,
  138,
  291,
  440,
  748,
  277,
  628,
  511,
  894,
  68,
  412,
  958,
  540,
  672,
  935,
  316,
  519,
  4,
  613,
  501,
  908,
  984,
  820,
  424,
  726,
  592,
  526,
  869,
  330,
  419,
  28,
  540,
  143,
  279,
  79,
  712,
  760,
  306,
  806,
  507,
  807,
  716,
  729,
  163,
  151,
  256,
  873,
  90,
  374,
  89,
  122,
  819,
  253,
  961,
  62,
  208,
  830,
  365,
  231,
  905,
  961,
  340,
  928,
  911,
  83,
  118,
  864,
  310,
  699,
  138,
  221,
  928,
  130,
  775,
  425,
  783,
  519,
  852,
  187,
  795,
  772,
  627,
  709,
  81,
  264,
  359,
  149,
  692,
  178,
  247,
  51,
  869,
  30,
  659,
  190,
  494,
  80,
  531,
  883,
  557,
  170,
  759,
  331,
  588,
  939,
  953,
  407,
  453,
  223,
  919,
  147,
  666,
  165,
  204,
  924,
  178,
  361,
  766,
  455,
  232,
  86,
  194,
  536,
  942,
  671,
  595,
  420,
  543,
  490,
  570,
  547,
  273,
  465,
  776,
  845,
  753,
  591,
  22,
  320,
  569,
  964,
  701,
  483,
  100,
  757,
  514,
  850,
  50,
  451,
  993,
  79,
  79,
  790,
  410,
  409,
  494,
  245,
  881,
  676,
  484,
  821,
  183,
  45,
  343,
  76,
  423,
  855,
  188,
  16,
  355,
  159,
  255,
  705,
  147,
  400,
  997,
  264,
  831,
  644,
  390,
  395,
  485,
  457,
  879,
  478,
  900,
  187,
  699,
  559,
  681,
  947,
  137,
  637,
  150,
  700,
  729,
  166,
  120,
  325,
  841,
  956,
  74,
  576,
  532,
  396,
  157,
  327,
  601,
  707,
  681,
  813,
  593,
  452,
  45,
  936,
  466,
  706,
  546,
  265,
  769,
  71,
  862,
  37,
  764,
  111,
  468,
  844,
  693,
  740,
  128,
  19,
  579,
  894,
  928,
  160,
  787,
  438,
  814,
  274,
  675,
  128,
  451,
  626,
  879,
  931,
  894,
  57,
  181,
  839,
  121,
  728,
  410,
  793,
  292,
  566,
  472,
  893,
  579,
  986,
  159,
  585,
  34,
  485,
  279,
  634,
  353,
  626,
  504,
  574,
  19,
  54,
  489,
  829,
  768,
  246,
  421,
  116,
  267,
  801,
  299,
  279,
  397,
  331,
  396,
  11,
  80,
  682,
  752,
  101,
  832,
  673,
  521,
  42,
  883,
  663,
  905,
  284,
  218,
  59,
  888,
  86,
  623,
  878,
  117,
  157,
  70,
  309,
  877,
  803,
  529,
  666,
  274,
  192,
  667,
  558,
  938,
  383,
  542,
  237,
  377,
  674,
  783,
  638,
  609,
  419,
  359,
  309,
  53,
  65,
  277,
  526,
  853,
  659,
  263,
  280,
  332,
  940,
  336,
  748,
  645,
  227,
  475,
  945,
  924,
  845,
  253,
  798,
  49,
  241,
  761,
  379,
  423,
  680,
  837,
  116,
  378,
  416,
  553,
  802,
  839,
  339,
  424,
  40,
  101,
  744,
  934,
  119,
  217,
  478,
  850,
  998,
  513,
  320,
  966,
  306,
  774,
  442,
  417,
  646,
  652,
  15,
  637,
  199,
  653,
  516,
  380,
  983,
  281,
  196,
  973,
  604,
  378,
  824,
  773,
  835,
  724,
  450,
  321,
  446,
  778,
  935,
  296,
  752,
  27,
  824,
  933,
  145,
  708,
  691,
  433,
  627,
  511,
  619,
  415,
  263,
  680,
  880,
  201,
  700,
  440,
  579,
  545,
  445,
  483,
  499,
  953,
  518,
  77,
  237,
  980,
  923,
  809,
  532,
  877,
  965,
  865,
  597,
  773,
  378,
  177,
  101,
  899,
  448,
  430,
  217,
  403,
  21,
  837,
  410,
  345,
  606,
  373,
  179,
  310,
  634,
  894,
  512,
  289,
  946,
  243,
  725,
  458,
  680,
  579,
  304,
  199,
  721,
  22,
  452,
  761,
  945,
  547,
  418,
  137,
  209,
  622,
  174,
  468,
  223,
  525,
  84,
  470,
  266,
  812,
  950,
  18,
  983,
  319,
  843,
  423,
  862,
  469,
  957,
  919,
  387,
  900,
  382,
  561,
  337,
  711,
  352,
  206,
  737,
  412,
  40,
  17,
  851,
  825,
  910,
  839,
  207,
  879,
  588,
  77,
  867,
  255,
  577,
  1,
  609,
  473,
  88,
  249,
  491,
  180,
  594,
  872,
  870,
  528,
  68,
  31,
  208,
  854,
  190,
  32,
  200,
  225,
  322,
  869,
  425,
  62,
  653,
  919,
  138,
  246,
  501,
  995,
  133,
  852,
  903,
  694,
  482,
  818,
  820,
  922,
  839,
  870,
  391,
  880,
  478,
  602,
  774,
  989,
  139,
  457,
  114,
  282,
  632,
  245,
  452,
  987,
  920,
  134,
  94,
  409,
  124,
  389,
  36,
  434,
  885,
  486,
  269,
  510,
  487,
  644,
  122,
  773,
  13,
  326,
  369,
  252,
  407,
  599,
  182,
  319,
  229,
  684,
  895,
  760,
  703,
  982,
  282,
  645,
  835,
  415,
  182,
  792,
  681,
  113,
  659,
  312,
  998,
  954,
  655,
  588,
  3,
  268,
  125,
  832,
  346,
  832,
  972,
  488,
  709,
  491,
  913,
  441,
  187,
  177,
  90,
  55,
  959,
  126,
  73,
  409,
  606,
  732,
  985,
  833,
  381,
  542,
  559,
  375,
  829,
  50,
  432,
  549,
  996,
  517,
  3,
  366,
  33,
  737,
  451,
  111,
  380,
  362,
  884,
  511,
  199,
  262,
  647,
  531,
  717,
  810,
  675,
  946,
  614,
  425,
  282,
  31,
  436,
  695,
  701,
  653,
  629,
  284,
  109,
  237,
  909,
  269,
  495,
  386,
  327,
  620,
  947,
  782,
  663,
  471,
  818,
  517,
  768,
  494,
  249,
  815,
  725,
  822,
  614,
  324,
  22,
  675,
  118,
  143,
  929,
  498,
  368,
  469,
  482,
  964,
  554,
  999,
  265,
  686,
  782,
  754,
  247,
  125,
  960,
  808,
  788,
  647,
  623,
  615,
  727,
  573,
  813,
  200,
  371,
  141,
  733,
  450,
  515,
  940,
  304,
  13,
  522,
  489,
  948,
  906,
  529,
  500,
  98,
  719,
  174,
  269,
  170,
  609,
  789,
  169,
  645,
  514,
  438,
  254,
  103,
  938,
  306,
  608,
  367,
  889,
  667,
  621,
  276,
  346,
  736,
  210,
  13,
  356,
  914,
  377,
  613,
  714,
  949,
  386,
  770,
  738,
  310,
  382,
  145,
  163,
  470,
  34,
  855,
  951,
  672,
  192,
  942,
  936,
  429,
  906,
  378,
  159,
  665,
  208,
  223,
  575,
  977,
  937,
  81,
  24,
  484,
  941,
  128,
  544,
  811,
  905,
  110,
  707,
  806,
  996,
  509,
  283,
  493,
  846,
  466,
  356,
  807,
  993,
  616,
  790,
  163,
  7,
  931,
  661,
  353,
  499,
  186,
  309,
  107,
  556,
  104,
  702,
  61,
  963,
  255,
  279,
  454,
  941,
  817,
  447,
  786,
  788,
  372,
  919,
  14,
  113,
  41,
  412,
  744,
  372,
  282,
  648,
  248,
  484,
  830,
  104,
  742,
  425,
  802,
  216,
  561,
  103,
  781,
  602,
  201,
  317,
  408,
  461,
  91,
  691,
  168,
  850,
  935,
  171,
  929,
  482,
  790,
  701,
  81,
  556,
  85,
  342,
  703,
  99,
  937,
  556,
  14,
  203,
  974,
  200,
  145,
  276,
  408,
  174,
  573,
  775,
  893,
  448,
  21,
  389,
  813,
  62,
  134,
  911,
  119,
  138,
  201,
  200,
  105,
  0,
  958,
  439,
  635,
  723,
  930,
  361,
  745,
  251,
  608,
  179,
  19,
  170,
  405,
  461,
  643,
  517,
  379,
  481,
  899,
  896,
  396,
  675,
  536,
  978,
  513,
  459,
  454,
  704,
  398,
  5,
  786,
  45,
  843,
  674,
  758,
  919,
  250,
  655,
  980,
  789,
  55,
  467,
  459,
  284,
  1,
  951,
  447,
  729,
  756,
  581,
  992,
  961,
  744,
  531,
  169,
  484,
  346,
  289,
  18,
  143,
  653,
  221,
  669,
  537,
  565,
  552,
  874,
  502,
  352,
  458,
  183,
  975,
  521,
  272,
  336,
  930,
  129,
  678,
  670,
  821,
  692,
  463,
  175,
  958,
  110,
  393,
  123,
  174,
  768,
  70,
  942,
  237,
  787,
  788,
  462,
  471,
  160,
  526,
  579,
  835,
  889,
  764,
  878,
  532,
  151,
  390,
  607,
  272,
  49,
  166,
  399,
  950,
  566,
  866,
  446,
  188,
  552,
  984,
  530,
  711,
  541,
  357,
  30,
  212,
  675,
  750,
  746,
  67,
  55,
  184,
  788,
  27,
  314,
  650,
  403,
  24,
  72,
  872,
  260,
  313,
  446,
  235,
  275,
  422,
  727,
  779,
  192,
  215,
  92,
  534,
  619,
  192,
  502,
  139,
  125,
  921,
  953,
  463,
  909,
  961,
  191,
  281,
  619,
  978,
  221,
  841,
  540,
  959,
  422,
  610,
  323,
  162,
  642,
  817,
  961,
  699,
  955,
  341,
  480,
  379,
  28,
  150,
  386,
  447,
  871,
  491,
  632,
  759,
  785,
  827,
  50,
  877,
  771,
  397,
  67,
  827,
  448,
  627,
  85,
  830,
  646,
  353,
  304,
  671,
  963,
  764,
  58,
  136,
  838,
  597,
  932,
  212,
  558,
  276,
  73,
  926,
  403,
  946,
  268,
  779,
  559,
  887,
  213,
  436,
  529,
  929,
  295,
  76,
  78,
  982,
  105,
  688,
  420,
  105,
  815,
  572,
  172,
  584,
  412,
  314,
  219,
  182,
  238,
  789,
  877,
  844,
  62,
  124,
  711,
  787,
  315,
  954,
  296,
  453,
  842,
  681,
  282,
  945,
  132,
  695,
  443,
  837,
  92,
  545,
  363,
  253,
  515,
  341,
  409,
  817,
  578,
  868,
  542,
  805,
  508,
  987,
  286,
  451,
  157,
  58,
  126,
  707,
  874,
  501,
  982,
  986,
  382,
  41,
  829,
  616,
  895,
  505,
  627,
  795,
  555,
  774,
  968,
  377,
  762,
  317,
  742,
  635,
  481,
  850,
  989,
  438,
  72,
  210,
  611,
  451,
  521,
  454,
  85,
  277,
  797,
  147,
  31,
  74,
  621,
  119,
  180,
  571,
  234,
  358,
  131,
  70,
  857,
  330,
  438,
  379,
  166,
  33,
  920,
  139,
  316,
  776,
  266,
  284,
  247,
  949,
  689,
  857,
  534,
  355,
  648,
  302,
  840,
  847,
  958,
  2,
  602,
  455,
  372,
  229,
  370,
  417,
  221,
  792,
  91,
  217,
  154,
  508,
  45,
  317,
  33,
  819,
  48,
  243,
  601,
  291,
  613,
  242,
  333,
  505,
  537,
  301,
  299,
  466,
  927,
  92,
  775,
  212,
  985,
  173,
  32,
  595,
  643,
  416,
  911,
  959,
  252,
  832,
  808,
  907,
  761,
  548,
  551,
  664,
  728,
  190,
  280,
  384,
  822,
  715,
  834,
  191,
  437,
  241,
  529,
  268,
  38,
  151,
  14,
  269,
  679,
  357,
  110,
  200,
  393,
  837,
  212,
  46,
  336,
  193,
  291,
  985,
  975,
  524,
  149,
  599,
  424,
  141,
  729,
  703,
  238,
  589,
  660,
  263,
  319,
  946,
  238,
  368,
  728,
  660,
  168,
  66,
  679,
  500,
  359,
  281,
  159,
  189,
  608,
  793,
  204,
  706,
  72,
  77,
  660,
  751,
  38,
  154,
  437,
  76,
  264,
  859,
  216,
  156,
  983,
  886,
  802,
  924,
  144,
  995,
  643,
  614,
  295,
  229,
  125,
  29,
  106,
  625,
  27,
  203,
  327,
  995,
  123,
  975,
  379,
  576,
  258,
  186,
  545,
  719,
  530,
  832,
  867,
  144,
  146,
  619,
  623,
  110,
  218,
  779,
  481,
  281,
  826,
  771,
  569,
  907,
  342,
  317,
  353,
  5,
  360,
  421,
  70,
  130,
  42,
  514,
  648,
  409,
  909,
  401,
  487,
  72,
  580,
  4,
  76,
  515,
  382,
  64,
  193,
  212,
  20,
  604,
  478,
  901,
  784,
  277,
  761,
  681,
  429,
  470,
  57,
  648,
  609,
  997,
  71,
  745,
  876,
  41,
  946,
  522,
  339,
  247,
  221,
  962,
  110,
  844,
  679,
  416,
  522,
  429,
  767,
  5,
  819,
  450,
  66,
  644,
  722,
  937,
  539,
  977,
  727,
  846,
  973,
  391,
  699,
  656,
  496,
  444,
  173,
  415,
  717,
  463,
  935,
  954,
  248,
  450,
  892,
  733,
  537,
  434,
  920,
  671,
  223,
  891,
  252,
  313,
  122,
  393,
  156,
  131,
  595,
  81,
  71,
  936,
  906,
  590,
  187,
  810,
  812,
  639,
  626,
  233,
  335,
  341,
  253,
  956,
  363,
  995,
  971,
  810,
  478,
  206,
  382,
  874,
  580,
  308,
  178,
  734,
  834,
  576,
  938,
  126,
  877,
  939,
  274,
  793,
  364,
  64,
  347,
  470,
  975,
  22,
  14,
  297,
  674,
  400,
  8,
  274,
  842,
  128,
  102,
  183,
  978,
  687,
  614,
  545,
  770,
  18,
  353,
  892,
  301,
  327,
  497,
  271,
  822,
  509,
  154,
  588,
  543,
  561,
  632,
  90,
  413,
  29,
  462,
  925,
  667,
  203,
  846,
  271,
  353,
  647,
  434,
  888,
  392,
  82,
  445,
  865,
  709,
  515,
  382,
  799,
  672,
  975,
  466,
  482,
  168,
  10,
  150,
  317,
  606,
  550,
  166,
  672,
  522,
  968,
  605,
  945,
  949,
  506,
  353,
  905,
  660,
  906,
  490,
  74,
  493,
  82,
  47,
  526,
  850,
  257,
  308,
  227,
  343,
  95,
  260,
  539,
  593,
  197,
  304,
  384,
  589,
  179,
  553,
  389,
  851,
  731,
  831,
  711,
  357,
  554,
  982,
  2,
  351,
  879,
  42,
  400,
  205,
  228,
  328,
  820,
  275,
  850,
  320,
  253,
  621,
  873,
  842,
  846,
  108,
  180,
  300,
  514,
  658,
  211,
  373,
  301,
  202,
  930,
  489,
  581,
  815,
  175,
  738,
  551,
  711,
  609,
  343,
  606,
  123,
  411,
  851,
  207,
  742,
  296,
  741,
  184,
  175,
  497,
  32,
  550,
  37,
  970,
  526,
  430,
  575,
  242,
  934,
  283,
  965,
  561,
  702,
  750,
  902,
  964,
  711,
  92,
  670,
  243,
  188,
  481,
  460,
  556,
  886,
  890,
  502,
  473,
  8,
  288,
  57,
  356,
  721,
  112,
  817,
  282,
  123,
  680,
  344,
  21,
  935,
  60,
  287,
  444,
  267,
  30,
  447,
  310,
  922,
  284,
  442,
  651,
  454,
  924,
  771,
  611,
  852,
  986,
  367,
  399,
  115,
  370,
  326,
  765,
  323,
  640,
  906,
  242,
  526,
  876,
  899,
  624,
  166,
  796,
  252,
  431,
  99,
  626,
  870,
  928,
  935,
  229,
  286,
  20,
  648,
  539,
  533,
  379,
  64,
  179,
  317,
  896,
  293,
  144,
  971,
  401,
  720,
  986,
  286,
  277,
  828,
  671,
  66,
  566,
  461,
  847,
  904,
  318,
  59,
  621,
  958,
  590,
  905,
  849,
  718,
  338,
  342,
  730,
  22,
  944,
  544,
  25,
  348,
  39,
  719,
  705,
  596,
  908,
  805,
  594,
  7,
  47,
  744,
  148,
  177,
  476,
  866,
  849,
  88,
  246,
  438,
  523,
  156,
  886,
  758,
  605,
  39,
  209,
  29,
  678,
  98,
  879,
  286,
  447,
  105,
  832,
  303,
  190,
  164,
  969,
  222,
  995,
  331,
  492,
  399,
  824,
  14,
  405,
  831,
  597,
  670,
  857,
  120,
  873,
  171,
  890,
  905,
  637,
  115,
  605,
  336,
  114,
  828,
  284,
  303,
  883,
  158,
  494,
  153,
  549,
  232,
  556,
  695,
  58,
  29,
  504,
  252,
  77,
  35,
  646,
  137,
  448,
  400,
  468,
  237,
  258,
  857,
  150,
  981,
  756,
  616,
  138,
  188,
  386,
  721,
  370,
  71,
  911,
  73,
  967,
  568,
  504,
  164,
  770,
  100,
  179,
  753,
  551,
  67,
  657,
  652,
  243,
  444,
  398,
  865,
  772,
  427,
  338,
  592,
  63,
  536,
  519,
  721,
  83,
  212,
  451,
  148,
  117,
  98,
  888,
  61,
  734,
  672,
  502,
  723,
  783,
  345,
  338,
  740,
  909,
  505,
  839,
  975,
  654,
  804,
  611,
  69,
  11,
  523,
  629,
  404,
  856,
  620,
  442,
  578,
  574,
  149,
  135,
  970,
  938,
  492,
  713,
  886,
  639,
  454,
  376,
  594,
  374,
  530,
  634,
  168,
  566,
  809,
  268,
  110,
  766,
  381,
  754,
  592,
  582,
  283,
  0,
  298,
  246,
  854,
  1,
  663,
  430,
  801,
  700,
  519,
  357,
  169,
  8,
  136,
  246,
  613,
  300,
  148,
  884,
  563,
  392,
  99,
  846,
  824,
  322,
  293,
  341,
  555,
  193,
  718,
  570,
  822,
  222,
  854,
  12,
  226,
  16,
  516,
  920,
  639,
  838,
  670,
  529,
  485,
  959,
  912,
  543,
  706,
  877,
  863,
  852,
  351,
  912,
  640,
  705,
  697,
  687,
  241,
  287,
  290,
  930,
  964,
  1
};
const int idx[2399] = {
  220,
  336,
  347,
  422,
  44,
  128,
  145,
  234,
  259,
  315,
  64,
  103,
  378,
  469,
  477,
  33,
  108,
  126,
  173,
  196,
  328,
  331,
  52,
  55,
  109,
  306,
  337,
  412,
  443,
  364,
  456,
  487,
  496,
  299,
  23,
  259,
  67,
  196,
  409,
  51,
  77,
  147,
  301,
  362,
  26,
  106,
  239,
  39,
  81,
  118,
  187,
  290,
  339,
  395,
  443,
  36,
  45,
  195,
  210,
  244,
  273,
  22,
  92,
  215,
  306,
  364,
  66,
  216,
  5,
  25,
  145,
  171,
  330,
  401,
  412,
  75,
  148,
  180,
  204,
  231,
  432,
  443,
  100,
  232,
  400,
  467,
  114,
  284,
  300,
  330,
  370,
  49,
  135,
  183,
  191,
  268,
  423,
  491,
  104,
  280,
  393,
  442,
  443,
  461,
  136,
  175,
  205,
  216,
  466,
  5,
  85,
  429,
  491,
  0,
  36,
  78,
  95,
  161,
  169,
  219,
  231,
  250,
  336,
  341,
  360,
  495,
  59,
  134,
  213,
  319,
  409,
  93,
  104,
  256,
  223,
  226,
  8,
  115,
  185,
  216,
  320,
  399,
  461,
  14,
  60,
  87,
  93,
  134,
  170,
  391,
  399,
  416,
  455,
  3,
  86,
  99,
  304,
  471,
  488,
  0,
  102,
  132,
  179,
  303,
  312,
  313,
  320,
  389,
  279,
  473,
  180,
  303,
  310,
  326,
  7,
  136,
  239,
  256,
  276,
  350,
  21,
  32,
  79,
  209,
  270,
  314,
  463,
  87,
  134,
  188,
  212,
  418,
  13,
  76,
  124,
  179,
  409,
  411,
  19,
  299,
  207,
  266,
  329,
  468,
  29,
  45,
  265,
  310,
  384,
  429,
  480,
  191,
  347,
  61,
  66,
  219,
  228,
  277,
  289,
  308,
  402,
  409,
  133,
  382,
  488,
  18,
  310,
  439,
  206,
  257,
  290,
  356,
  443,
  43,
  140,
  184,
  187,
  278,
  286,
  341,
  354,
  126,
  201,
  208,
  239,
  454,
  485,
  40,
  87,
  222,
  367,
  398,
  457,
  299,
  423,
  440,
  44,
  115,
  126,
  147,
  291,
  411,
  64,
  480,
  1,
  67,
  80,
  91,
  163,
  239,
  42,
  350,
  361,
  427,
  67,
  169,
  270,
  15,
  44,
  223,
  378,
  452,
  471,
  31,
  67,
  274,
  292,
  457,
  58,
  107,
  183,
  222,
  347,
  407,
  27,
  65,
  84,
  208,
  273,
  385,
  441,
  43,
  97,
  226,
  305,
  360,
  492,
  26,
  88,
  284,
  369,
  476,
  21,
  48,
  478,
  230,
  312,
  409,
  475,
  42,
  53,
  78,
  259,
  268,
  489,
  3,
  37,
  60,
  141,
  132,
  150,
  157,
  328,
  353,
  357,
  422,
  466,
  480,
  154,
  455,
  295,
  411,
  249,
  320,
  359,
  381,
  401,
  451,
  210,
  231,
  253,
  323,
  330,
  5,
  55,
  79,
  105,
  298,
  496,
  160,
  229,
  425,
  30,
  63,
  115,
  129,
  280,
  458,
  31,
  68,
  254,
  360,
  420,
  490,
  2,
  172,
  180,
  209,
  223,
  228,
  265,
  357,
  369,
  380,
  443,
  453,
  483,
  36,
  110,
  129,
  135,
  246,
  305,
  36,
  211,
  239,
  254,
  392,
  403,
  494,
  255,
  332,
  485,
  110,
  360,
  498,
  0,
  11,
  37,
  106,
  182,
  308,
  14,
  41,
  75,
  218,
  256,
  259,
  294,
  462,
  218,
  231,
  248,
  392,
  427,
  21,
  234,
  406,
  29,
  171,
  248,
  255,
  352,
  34,
  57,
  122,
  173,
  254,
  308,
  380,
  393,
  278,
  28,
  62,
  129,
  296,
  455,
  474,
  15,
  47,
  128,
  133,
  300,
  390,
  459,
  468,
  35,
  48,
  70,
  287,
  299,
  318,
  22,
  108,
  171,
  195,
  460,
  496,
  188,
  21,
  31,
  86,
  338,
  420,
  422,
  486,
  495,
  245,
  445,
  22,
  85,
  92,
  337,
  381,
  387,
  7,
  9,
  231,
  425,
  430,
  56,
  196,
  344,
  354,
  377,
  91,
  107,
  177,
  221,
  295,
  321,
  5,
  35,
  48,
  90,
  290,
  432,
  447,
  51,
  322,
  324,
  364,
  482,
  59,
  303,
  334,
  444,
  450,
  55,
  125,
  319,
  380,
  394,
  431,
  82,
  112,
  157,
  187,
  261,
  326,
  347,
  366,
  18,
  124,
  490,
  8,
  218,
  291,
  35,
  132,
  322,
  425,
  147,
  150,
  242,
  472,
  186,
  195,
  201,
  216,
  251,
  458,
  33,
  46,
  153,
  297,
  298,
  311,
  322,
  399,
  426,
  65,
  230,
  9,
  32,
  69,
  391,
  70,
  126,
  147,
  222,
  86,
  261,
  412,
  183,
  474,
  110,
  125,
  172,
  185,
  402,
  363,
  403,
  462,
  40,
  274,
  386,
  449,
  333,
  340,
  421,
  424,
  410,
  30,
  86,
  262,
  374,
  23,
  72,
  9,
  47,
  86,
  93,
  286,
  304,
  402,
  420,
  118,
  265,
  276,
  283,
  455,
  20,
  36,
  391,
  115,
  137,
  305,
  334,
  10,
  188,
  237,
  271,
  393,
  422,
  497,
  21,
  30,
  99,
  109,
  175,
  198,
  467,
  3,
  19,
  63,
  82,
  115,
  149,
  265,
  24,
  151,
  217,
  252,
  307,
  421,
  146,
  333,
  381,
  434,
  32,
  311,
  361,
  93,
  142,
  152,
  395,
  422,
  467,
  91,
  181,
  244,
  294,
  332,
  390,
  97,
  177,
  296,
  323,
  428,
  27,
  215,
  318,
  66,
  193,
  216,
  333,
  416,
  127,
  171,
  209,
  219,
  333,
  377,
  401,
  9,
  103,
  129,
  135,
  290,
  438,
  33,
  107,
  221,
  351,
  392,
  406,
  91,
  170,
  182,
  313,
  419,
  465,
  28,
  74,
  175,
  231,
  270,
  30,
  34,
  240,
  253,
  63,
  133,
  337,
  369,
  416,
  255,
  445,
  145,
  350,
  416,
  183,
  257,
  414,
  136,
  164,
  255,
  300,
  434,
  438,
  447,
  60,
  157,
  396,
  412,
  25,
  343,
  42,
  105,
  361,
  472,
  34,
  74,
  136,
  436,
  474,
  94,
  177,
  205,
  225,
  227,
  319,
  23,
  245,
  383,
  426,
  31,
  190,
  215,
  228,
  324,
  416,
  7,
  12,
  260,
  470,
  13,
  290,
  9,
  44,
  117,
  166,
  186,
  260,
  361,
  372,
  224,
  241,
  369,
  1,
  87,
  297,
  457,
  29,
  98,
  118,
  158,
  226,
  286,
  74,
  167,
  241,
  328,
  370,
  412,
  454,
  1,
  37,
  183,
  228,
  311,
  336,
  345,
  413,
  430,
  446,
  211,
  327,
  375,
  84,
  195,
  219,
  430,
  447,
  195,
  384,
  50,
  93,
  224,
  349,
  479,
  6,
  56,
  105,
  118,
  170,
  286,
  468,
  466,
  153,
  224,
  240,
  400,
  444,
  63,
  158,
  196,
  237,
  284,
  296,
  405,
  407,
  480,
  26,
  56,
  233,
  428,
  370,
  398,
  491,
  159,
  184,
  488,
  131,
  134,
  138,
  276,
  344,
  372,
  428,
  494,
  269,
  486,
  136,
  139,
  163,
  201,
  253,
  272,
  374,
  398,
  487,
  307,
  375,
  487,
  168,
  284,
  346,
  420,
  451,
  134,
  175,
  284,
  88,
  105,
  286,
  448,
  96,
  117,
  177,
  240,
  285,
  325,
  455,
  51,
  228,
  298,
  421,
  150,
  433,
  182,
  362,
  410,
  58,
  262,
  352,
  439,
  43,
  70,
  134,
  278,
  152,
  210,
  283,
  310,
  333,
  334,
  469,
  20,
  42,
  69,
  222,
  283,
  320,
  330,
  376,
  218,
  285,
  413,
  434,
  5,
  175,
  180,
  265,
  440,
  474,
  241,
  255,
  377,
  479,
  307,
  317,
  457,
  0,
  232,
  342,
  496,
  25,
  292,
  105,
  169,
  208,
  300,
  439,
  21,
  65,
  120,
  249,
  273,
  191,
  302,
  376,
  56,
  92,
  240,
  371,
  391,
  446,
  489,
  84,
  241,
  322,
  473,
  475,
  16,
  92,
  214,
  239,
  50,
  158,
  175,
  452,
  51,
  360,
  25,
  39,
  90,
  99,
  133,
  408,
  491,
  430,
  12,
  64,
  76,
  189,
  481,
  128,
  306,
  442,
  77,
  276,
  337,
  356,
  380,
  389,
  445,
  61,
  158,
  194,
  445,
  303,
  398,
  143,
  163,
  199,
  343,
  236,
  246,
  340,
  382,
  446,
  38,
  154,
  196,
  202,
  266,
  367,
  369,
  117,
  136,
  250,
  272,
  413,
  481,
  0,
  199,
  205,
  412,
  39,
  177,
  198,
  369,
  448,
  91,
  153,
  167,
  187,
  203,
  265,
  328,
  218,
  222,
  261,
  413,
  419,
  447,
  128,
  228,
  498,
  0,
  148,
  198,
  486,
  497,
  50,
  398,
  457,
  283,
  460,
  43,
  116,
  246,
  248,
  305,
  447,
  106,
  131,
  317,
  126,
  199,
  235,
  293,
  34,
  108,
  226,
  3,
  108,
  129,
  155,
  174,
  162,
  239,
  490,
  124,
  214,
  346,
  469,
  497,
  274,
  316,
  122,
  144,
  149,
  290,
  337,
  362,
  371,
  466,
  67,
  248,
  276,
  332,
  360,
  387,
  405,
  31,
  56,
  65,
  90,
  200,
  64,
  176,
  203,
  215,
  236,
  240,
  337,
  383,
  198,
  411,
  431,
  36,
  90,
  350,
  356,
  497,
  33,
  120,
  130,
  183,
  409,
  493,
  8,
  35,
  254,
  277,
  321,
  341,
  388,
  423,
  497,
  143,
  163,
  391,
  446,
  492,
  9,
  270,
  42,
  52,
  116,
  396,
  456,
  478,
  491,
  143,
  148,
  286,
  328,
  384,
  35,
  127,
  351,
  452,
  7,
  46,
  259,
  35,
  290,
  370,
  420,
  104,
  258,
  278,
  340,
  481,
  169,
  264,
  368,
  232,
  471,
  1,
  135,
  211,
  152,
  174,
  177,
  187,
  292,
  411,
  430,
  461,
  4,
  92,
  205,
  237,
  247,
  333,
  53,
  91,
  289,
  334,
  425,
  491,
  118,
  175,
  490,
  36,
  361,
  33,
  186,
  213,
  471,
  3,
  73,
  163,
  409,
  235,
  384,
  410,
  470,
  480,
  59,
  469,
  97,
  344,
  372,
  33,
  107,
  179,
  397,
  470,
  291,
  340,
  361,
  385,
  25,
  111,
  158,
  331,
  471,
  28,
  87,
  307,
  69,
  105,
  159,
  284,
  311,
  312,
  359,
  465,
  17,
  133,
  302,
  324,
  274,
  325,
  421,
  252,
  4,
  96,
  409,
  206,
  246,
  288,
  58,
  81,
  150,
  226,
  232,
  380,
  168,
  229,
  367,
  210,
  248,
  405,
  420,
  163,
  212,
  320,
  340,
  448,
  68,
  222,
  439,
  494,
  70,
  94,
  116,
  471,
  284,
  380,
  13,
  26,
  120,
  276,
  394,
  432,
  492,
  281,
  297,
  300,
  355,
  29,
  32,
  156,
  182,
  467,
  203,
  234,
  420,
  429,
  210,
  224,
  248,
  273,
  326,
  349,
  37,
  202,
  377,
  380,
  43,
  55,
  139,
  141,
  170,
  232,
  292,
  322,
  77,
  214,
  241,
  279,
  326,
  18,
  46,
  55,
  107,
  227,
  238,
  250,
  146,
  168,
  402,
  444,
  459,
  487,
  495,
  6,
  121,
  256,
  303,
  457,
  461,
  69,
  122,
  193,
  204,
  240,
  347,
  412,
  418,
  476,
  169,
  187,
  400,
  97,
  290,
  364,
  394,
  153,
  184,
  187,
  9,
  13,
  65,
  89,
  120,
  221,
  484,
  6,
  120,
  180,
  419,
  15,
  86,
  104,
  193,
  276,
  324,
  437,
  443,
  62,
  97,
  193,
  288,
  315,
  318,
  414,
  24,
  170,
  189,
  196,
  216,
  228,
  270,
  420,
  214,
  407,
  466,
  2,
  77,
  127,
  188,
  230,
  310,
  464,
  469,
  80,
  204,
  138,
  171,
  252,
  424,
  0,
  95,
  363,
  395,
  408,
  430,
  96,
  143,
  289,
  97,
  183,
  341,
  399,
  460,
  84,
  243,
  498,
  28,
  65,
  77,
  84,
  139,
  147,
  171,
  214,
  256,
  348,
  408,
  444,
  449,
  457,
  120,
  342,
  38,
  217,
  465,
  8,
  212,
  268,
  346,
  486,
  491,
  49,
  77,
  90,
  222,
  291,
  383,
  130,
  405,
  431,
  473,
  78,
  290,
  351,
  189,
  304,
  498,
  336,
  10,
  219,
  257,
  402,
  437,
  65,
  69,
  168,
  198,
  65,
  241,
  242,
  290,
  360,
  402,
  254,
  256,
  398,
  407,
  66,
  97,
  164,
  222,
  316,
  390,
  429,
  24,
  81,
  133,
  207,
  313,
  67,
  108,
  204,
  303,
  494,
  43,
  194,
  198,
  285,
  294,
  347,
  356,
  394,
  83,
  92,
  147,
  167,
  386,
  20,
  225,
  400,
  172,
  363,
  99,
  64,
  373,
  377,
  6,
  63,
  206,
  107,
  149,
  230,
  428,
  41,
  56,
  77,
  78,
  311,
  413,
  476,
  477,
  81,
  130,
  145,
  167,
  247,
  416,
  56,
  289,
  339,
  27,
  47,
  132,
  309,
  392,
  36,
  55,
  73,
  352,
  358,
  25,
  58,
  352,
  430,
  58,
  171,
  221,
  334,
  379,
  453,
  288,
  479,
  109,
  134,
  143,
  174,
  285,
  313,
  468,
  495,
  258,
  289,
  334,
  382,
  483,
  46,
  136,
  264,
  417,
  458,
  36,
  59,
  88,
  173,
  310,
  316,
  354,
  471,
  46,
  225,
  262,
  335,
  364,
  468,
  121,
  341,
  349,
  7,
  14,
  21,
  99,
  135,
  142,
  207,
  209,
  272,
  294,
  456,
  491,
  208,
  248,
  321,
  43,
  129,
  188,
  362,
  191,
  279,
  294,
  307,
  324,
  362,
  140,
  422,
  56,
  169,
  188,
  232,
  328,
  449,
  14,
  134,
  369,
  375,
  48,
  164,
  224,
  260,
  20,
  93,
  157,
  219,
  262,
  274,
  362,
  473,
  484,
  103,
  125,
  140,
  174,
  175,
  191,
  226,
  358,
  408,
  450,
  20,
  94,
  289,
  310,
  311,
  448,
  478,
  36,
  175,
  185,
  337,
  391,
  48,
  72,
  184,
  233,
  345,
  485,
  231,
  242,
  339,
  451,
  456,
  152,
  158,
  398,
  458,
  488,
  151,
  240,
  357,
  1,
  33,
  139,
  141,
  177,
  223,
  289,
  479,
  90,
  115,
  461,
  480,
  24,
  26,
  44,
  72,
  213,
  361,
  445,
  34,
  119,
  470,
  19,
  56,
  405,
  464,
  47,
  112,
  163,
  235,
  342,
  462,
  103,
  192,
  225,
  23,
  458,
  68,
  270,
  363,
  422,
  427,
  449,
  450,
  477,
  105,
  131,
  139,
  198,
  212,
  413,
  429,
  435,
  43,
  278,
  19,
  113,
  192,
  327,
  347,
  44,
  67,
  160,
  225,
  263,
  330,
  344,
  158,
  274,
  303,
  317,
  350,
  379,
  409,
  33,
  53,
  217,
  273,
  304,
  352,
  461,
  495,
  101,
  168,
  370,
  395,
  458,
  156,
  301,
  319,
  324,
  347,
  73,
  127,
  253,
  272,
  128,
  212,
  237,
  257,
  351,
  77,
  106,
  216,
  270,
  368,
  371,
  400,
  223,
  355,
  384,
  30,
  268,
  307,
  368,
  79,
  300,
  317,
  327,
  15,
  376,
  31,
  80,
  160,
  206,
  227,
  103,
  231,
  435,
  481,
  499,
  182,
  186,
  189,
  442,
  7,
  59,
  65,
  117,
  225,
  298,
  304,
  364,
  457,
  489,
  186,
  198,
  265,
  309,
  336,
  391,
  457,
  314,
  418,
  81,
  133,
  186,
  190,
  227,
  258,
  277,
  419,
  492,
  82,
  222,
  239,
  315,
  71,
  92,
  122,
  220,
  252,
  272,
  311,
  391,
  433,
  97,
  137,
  244,
  267,
  426,
  34,
  202,
  234,
  426,
  428,
  51,
  109,
  267,
  377,
  382,
  107,
  166,
  203,
  337,
  0,
  127,
  247,
  404,
  64,
  94,
  373,
  430,
  448,
  17,
  37,
  57,
  102,
  352,
  354,
  114,
  174,
  193,
  241,
  284,
  74,
  94,
  213,
  238,
  475,
  476,
  140,
  247,
  280,
  302,
  328,
  49,
  197,
  201,
  222,
  280,
  457,
  167,
  445,
  465,
  478,
  499,
  25,
  215,
  438,
  8,
  129,
  153,
  171,
  316,
  328,
  158,
  215,
  303,
  328,
  353,
  479,
  62,
  251,
  271,
  4,
  119,
  262,
  303,
  311,
  405,
  419,
  277,
  461,
  236,
  248,
  445,
  15,
  108,
  227,
  309,
  362,
  378,
  424,
  78,
  94,
  109,
  118,
  124,
  247,
  253,
  315,
  478,
  13,
  154,
  170,
  331,
  365,
  386,
  264,
  268,
  300,
  305,
  429,
  463,
  499,
  52,
  105,
  135,
  181,
  111,
  156,
  183,
  231,
  350,
  388,
  461,
  291,
  360,
  80,
  106,
  138,
  197,
  242,
  255,
  260,
  381,
  415,
  447,
  499,
  41,
  266,
  341,
  391,
  410,
  448,
  495,
  58,
  146,
  286,
  351,
  419,
  436,
  464,
  483,
  251,
  252,
  444,
  492,
  184,
  200,
  57,
  75,
  170,
  186,
  187,
  275,
  314,
  364,
  407,
  162,
  173,
  232,
  211,
  355,
  445,
  448,
  308,
  98,
  280,
  397,
  431,
  112,
  122,
  157,
  209,
  338,
  388,
  429,
  112,
  213,
  349,
  470,
  69,
  70,
  119,
  222,
  251,
  453,
  81,
  173,
  482,
  105,
  147,
  10,
  229,
  462,
  467,
  98,
  421,
  479,
  203,
  498,
  499,
  93,
  130,
  142,
  270,
  278,
  336,
  419,
  73,
  134,
  142,
  177,
  192,
  335,
  490,
  45,
  140,
  143,
  195,
  274,
  284,
  324,
  56,
  94,
  171,
  28,
  135,
  258,
  277,
  284,
  333,
  370,
  421,
  432,
  465,
  31,
  46,
  222,
  331,
  387,
  432,
  18,
  56,
  82,
  95,
  258,
  261,
  356,
  378,
  484,
  60,
  285,
  298,
  347,
  0,
  200,
  307,
  372,
  2,
  89,
  201,
  291,
  298,
  382,
  455,
  121,
  145,
  155,
  47,
  226,
  236,
  396,
  398,
  137,
  311,
  381,
  429,
  45,
  109,
  141,
  173,
  207,
  464,
  471,
  499,
  37,
  45,
  268,
  447,
  496,
  41,
  163,
  387,
  484,
  30,
  48,
  91,
  146,
  261,
  313,
  401,
  11,
  78,
  122,
  144,
  450,
  499,
  75,
  82,
  131,
  218,
  257,
  285,
  294,
  362,
  442,
  213,
  255,
  291,
  492,
  63,
  80,
  282,
  418,
  1,
  60,
  87,
  102,
  111,
  180,
  272,
  281,
  324,
  380,
  458,
  185,
  216,
  475,
  12,
  62,
  109,
  143,
  195,
  257,
  271,
  324,
  385,
  410,
  226,
  330,
  404,
  54,
  158,
  374,
  221,
  320,
  340,
  86,
  93,
  236,
  94,
  159,
  238,
  242,
  318,
  356,
  40,
  75,
  168,
  211,
  294,
  32,
  164,
  174,
  198,
  421,
  13,
  102,
  314,
  379,
  418,
  439,
  485,
  6,
  53,
  104,
  123,
  208,
  436,
  452,
  59,
  141,
  204,
  402,
  498,
  134,
  335,
  429,
  240,
  391,
  461,
  14,
  16,
  46,
  371,
  376,
  37,
  172,
  227,
  343,
  397,
  435,
  39,
  136,
  202,
  262,
  339,
  445,
  474,
  145,
  272,
  342,
  121,
  127,
  12,
  125,
  155,
  186,
  234,
  64,
  96,
  97,
  108,
  213,
  350,
  410,
  485,
  35,
  56,
  57,
  167,
  169,
  399,
  478,
  60,
  103,
  307,
  92,
  104,
  150,
  211,
  260,
  8,
  64,
  73,
  222,
  273,
  423,
  179,
  184,
  190,
  193,
  265,
  271,
  305,
  318,
  344,
  14,
  75,
  124,
  317,
  343,
  404,
  4,
  141,
  167,
  212,
  496
};
const double x[500] = {
  737,
  519,
  538,
  486,
  557,
  31,
  651,
  101,
  310,
  729,
  721,
  164,
  577,
  411,
  104,
  891,
  988,
  370,
  788,
  898,
  576,
  674,
  7,
  10,
  91,
  253,
  9,
  54,
  105,
  36,
  799,
  188,
  651,
  92,
  766,
  394,
  8,
  823,
  242,
  334,
  639,
  462,
  111,
  847,
  919,
  681,
  392,
  657,
  358,
  203,
  453,
  897,
  965,
  316,
  759,
  894,
  893,
  44,
  743,
  736,
  970,
  473,
  229,
  120,
  485,
  174,
  405,
  514,
  984,
  200,
  723,
  867,
  259,
  997,
  191,
  340,
  75,
  763,
  579,
  216,
  154,
  331,
  338,
  184,
  786,
  56,
  235,
  880,
  810,
  544,
  522,
  358,
  219,
  566,
  632,
  422,
  636,
  760,
  657,
  117,
  138,
  228,
  163,
  336,
  572,
  722,
  438,
  280,
  234,
  454,
  967,
  148,
  325,
  142,
  790,
  3,
  497,
  770,
  936,
  101,
  696,
  108,
  255,
  140,
  320,
  29,
  36,
  228,
  468,
  24,
  183,
  844,
  513,
  856,
  102,
  9,
  526,
  50,
  73,
  366,
  599,
  246,
  662,
  473,
  651,
  568,
  575,
  972,
  352,
  341,
  897,
  15,
  73,
  764,
  768,
  879,
  886,
  906,
  718,
  621,
  529,
  282,
  339,
  165,
  137,
  999,
  215,
  33,
  639,
  999,
  906,
  210,
  62,
  655,
  996,
  675,
  552,
  333,
  176,
  426,
  891,
  638,
  571,
  715,
  18,
  708,
  795,
  26,
  31,
  250,
  18,
  949,
  183,
  968,
  394,
  580,
  766,
  686,
  162,
  134,
  185,
  943,
  919,
  577,
  539,
  180,
  750,
  285,
  591,
  881,
  381,
  118,
  852,
  696,
  617,
  941,
  767,
  592,
  650,
  74,
  961,
  881,
  891,
  71,
  905,
  575,
  598,
  523,
  477,
  561,
  948,
  762,
  570,
  773,
  146,
  894,
  203,
  610,
  471,
  669,
  189,
  473,
  650,
  606,
  385,
  288,
  360,
  648,
  115,
  836,
  139,
  530,
  248,
  331,
  286,
  849,
  812,
  356,
  884,
  33,
  57,
  147,
  297,
  826,
  916,
  581,
  0,
  918,
  81,
  12,
  956,
  309,
  550,
  15,
  243,
  294,
  893,
  290,
  227,
  826,
  843,
  789,
  744,
  494,
  742,
  643,
  126,
  861,
  444,
  506,
  417,
  215,
  246,
  9,
  244,
  283,
  595,
  635,
  494,
  612,
  737,
  311,
  896,
  834,
  222,
  121,
  595,
  680,
  309,
  729,
  263,
  142,
  804,
  262,
  343,
  179,
  649,
  118,
  360,
  536,
  669,
  429,
  359,
  667,
  313,
  671,
  506,
  951,
  461,
  291,
  359,
  237,
  727,
  143,
  968,
  769,
  97,
  842,
  752,
  803,
  299,
  154,
  384,
  23,
  567,
  339,
  778,
  492,
  116,
  320,
  967,
  526,
  66,
  761,
  908,
  345,
  885,
  193,
  894,
  547,
  124,
  18,
  254,
  947,
  192,
  111,
  384,
  204,
  338,
  574,
  749,
  816,
  717,
  457,
  353,
  163,
  979,
  896,
  679,
  342,
  932,
  100,
  216,
  531,
  320,
  122,
  594,
  956,
  638,
  450,
  733,
  643,
  293,
  891,
  633,
  901,
  815,
  676,
  307,
  144,
  286,
  106,
  182,
  605,
  575,
  129,
  390,
  212,
  843,
  225,
  544,
  468,
  203,
  223,
  862,
  795,
  36,
  348,
  743,
  528,
  904,
  126,
  802,
  82,
  156,
  369,
  986,
  332,
  977,
  570,
  421,
  345,
  401,
  480,
  63,
  518,
  667,
  31,
  909,
  552,
  994,
  314,
  891,
  642,
  439,
  132,
  670,
  402,
  263,
  140,
  549,
  905,
  712,
  299,
  986,
  86,
  709,
  786,
  47,
  679,
  864,
  13,
  140,
  659,
  479,
  838,
  988,
  846,
  855,
  367,
  935,
  657,
  453,
  400,
  851,
  749,
  500,
  673,
  523,
  708,
  568,
  76,
  18,
  589,
  689,
  195,
  504,
  402,
  835,
  705,
  187,
  615,
  482,
  160,
  609,
  761,
  907,
  294,
  538,
  545
};
const int ptr[501] = {
  0,
  4,
  8,
  10,
  15,
  22,
  29,
  33,
  34,
  36,
  39,
  44,
  44,
  47,
  55,
  61,
  66,
  68,
  75,
  82,
  86,
  91,
  98,
  104,
  109,
  113,
  126,
  131,
  134,
  136,
  143,
  153,
  159,
  168,
  170,
  174,
  176,
  180,
  187,
  192,
  198,
  200,
  204,
  211,
  213,
  222,
  225,
  228,
  233,
  241,
  247,
  253,
  256,
  262,
  264,
  270,
  274,
  277,
  283,
  288,
  294,
  301,
  307,
  312,
  315,
  319,
  325,
  329,
  332,
  338,
  340,
  342,
  348,
  353,
  359,
  362,
  366,
  368,
  374,
  387,
  393,
  400,
  403,
  406,
  412,
  420,
  425,
  428,
  433,
  441,
  442,
  448,
  456,
  462,
  468,
  469,
  477,
  479,
  485,
  490,
  495,
  501,
  508,
  513,
  518,
  524,
  532,
  535,
  538,
  542,
  546,
  552,
  561,
  563,
  567,
  571,
  574,
  576,
  581,
  584,
  588,
  592,
  593,
  597,
  599,
  607,
  612,
  615,
  619,
  626,
  633,
  640,
  646,
  650,
  653,
  659,
  665,
  670,
  673,
  678,
  685,
  691,
  697,
  703,
  708,
  712,
  717,
  719,
  722,
  725,
  732,
  736,
  738,
  742,
  747,
  753,
  757,
  763,
  767,
  769,
  769,
  777,
  780,
  784,
  790,
  797,
  807,
  810,
  813,
  815,
  817,
  822,
  829,
  830,
  835,
  844,
  848,
  851,
  854,
  862,
  864,
  873,
  876,
  881,
  884,
  888,
  895,
  899,
  901,
  904,
  908,
  912,
  919,
  927,
  931,
  937,
  941,
  944,
  948,
  950,
  955,
  960,
  963,
  970,
  975,
  979,
  983,
  985,
  992,
  993,
  998,
  1001,
  1008,
  1012,
  1014,
  1018,
  1023,
  1030,
  1036,
  1040,
  1045,
  1052,
  1058,
  1061,
  1066,
  1069,
  1071,
  1077,
  1080,
  1084,
  1087,
  1090,
  1092,
  1095,
  1100,
  1102,
  1110,
  1117,
  1122,
  1130,
  1133,
  1138,
  1142,
  1144,
  1146,
  1153,
  1158,
  1160,
  1167,
  1172,
  1176,
  1179,
  1183,
  1188,
  1191,
  1193,
  1196,
  1204,
  1210,
  1216,
  1219,
  1221,
  1225,
  1229,
  1234,
  1236,
  1239,
  1244,
  1248,
  1253,
  1256,
  1264,
  1268,
  1271,
  1272,
  1275,
  1278,
  1284,
  1287,
  1291,
  1296,
  1300,
  1304,
  1306,
  1313,
  1317,
  1322,
  1326,
  1332,
  1336,
  1344,
  1349,
  1356,
  1363,
  1368,
  1369,
  1378,
  1381,
  1385,
  1388,
  1395,
  1399,
  1407,
  1414,
  1422,
  1425,
  1433,
  1435,
  1438,
  1439,
  1445,
  1448,
  1450,
  1453,
  1456,
  1470,
  1472,
  1475,
  1481,
  1487,
  1491,
  1494,
  1497,
  1498,
  1503,
  1507,
  1513,
  1517,
  1524,
  1529,
  1534,
  1542,
  1547,
  1550,
  1550,
  1552,
  1553,
  1556,
  1559,
  1563,
  1571,
  1577,
  1580,
  1585,
  1590,
  1594,
  1598,
  1600,
  1602,
  1610,
  1615,
  1620,
  1628,
  1634,
  1637,
  1649,
  1652,
  1656,
  1662,
  1664,
  1670,
  1674,
  1678,
  1687,
  1697,
  1704,
  1709,
  1715,
  1720,
  1725,
  1728,
  1736,
  1740,
  1747,
  1750,
  1754,
  1760,
  1763,
  1765,
  1773,
  1781,
  1783,
  1788,
  1795,
  1802,
  1810,
  1815,
  1820,
  1824,
  1829,
  1836,
  1839,
  1843,
  1847,
  1849,
  1854,
  1859,
  1863,
  1873,
  1880,
  1882,
  1891,
  1895,
  1899,
  1904,
  1909,
  1914,
  1919,
  1923,
  1927,
  1932,
  1938,
  1943,
  1949,
  1954,
  1960,
  1965,
  1968,
  1974,
  1980,
  1983,
  1990,
  1992,
  1995,
  2002,
  2011,
  2017,
  2024,
  2028,
  2035,
  2037,
  2048,
  2055,
  2063,
  2067,
  2069,
  2078,
  2081,
  2085,
  2086,
  2090,
  2097,
  2101,
  2107,
  2110,
  2112,
  2116,
  2119,
  2122,
  2129,
  2136,
  2143,
  2146,
  2156,
  2162,
  2171,
  2175,
  2179,
  2186,
  2189,
  2194,
  2198,
  2206,
  2211,
  2215,
  2222,
  2228,
  2237,
  2241,
  2245,
  2256,
  2259,
  2269,
  2272,
  2275,
  2278,
  2279,
  2281,
  2287,
  2292,
  2297,
  2304,
  2311,
  2316,
  2319,
  2322,
  2327,
  2333,
  2340,
  2343,
  2345,
  2350,
  2358,
  2365,
  2365,
  2368,
  2373,
  2379,
  2388,
  2394,
  2399
};
const double verify_data[500] = {
  1636962,
  1714376,
  142636,
  1151015,
  1672341,
  2790420,
  1447201,
  422892,
  30953,
  1030287,
  1335188,
  0,
  605334,
  2278445,
  858848,
  245423,
  950882,
  705076,
  1312024,
  1084284,
  1837558,
  1201746,
  2360392,
  1488940,
  688178,
  2632122,
  1481444,
  660854,
  346453,
  982949,
  1400599,
  1093225,
  2856372,
  1078398,
  1074402,
  579548,
  1820752,
  2638601,
  2072665,
  749887,
  687788,
  478788,
  1482258,
  1207317,
  1397243,
  794364,
  1002505,
  1651686,
  1028801,
  1189726,
  1513197,
  1214956,
  738475,
  633771,
  1207042,
  680857,
  899314,
  2277406,
  773143,
  1986687,
  907216,
  907940,
  1539019,
  1043338,
  681730,
  219905,
  1397298,
  2184201,
  1537202,
  266744,
  563005,
  1827909,
  1105928,
  2286680,
  887533,
  343193,
  238910,
  1678393,
  2600003,
  417502,
  1551071,
  798273,
  398719,
  2056881,
  1296314,
  917292,
  190534,
  882078,
  1979139,
  50621,
  1048185,
  1967771,
  1911887,
  1895897,
  23343,
  2658748,
  285864,
  1027049,
  975769,
  2488413,
  832738,
  844130,
  1379856,
  1785889,
  2463463,
  782430,
  982466,
  609500,
  706251,
  1981399,
  1861430,
  2146667,
  250104,
  1166284,
  1295022,
  189599,
  855191,
  1005718,
  969658,
  707377,
  561273,
  86496,
  717937,
  97767,
  1893638,
  779229,
  429727,
  99564,
  1863565,
  2267656,
  950026,
  780700,
  581248,
  393282,
  2134865,
  1244700,
  1894843,
  954212,
  1439102,
  779512,
  1459287,
  881497,
  2202043,
  1447401,
  1249637,
  765168,
  488244,
  837127,
  1236555,
  2281259,
  1995666,
  25783,
  534020,
  1486259,
  1268571,
  875283,
  744594,
  1410335,
  757320,
  0,
  1922627,
  399058,
  1490594,
  1475527,
  1587557,
  1695667,
  644546,
  536038,
  224304,
  414120,
  2029077,
  3930385,
  377416,
  1059074,
  1960417,
  1439575,
  368749,
  460183,
  2479302,
  105204,
  1426355,
  649313,
  2194338,
  918200,
  1591449,
  2229266,
  434520,
  684504,
  1009270,
  222922,
  600674,
  1011867,
  1321434,
  836127,
  2493805,
  1448674,
  1269364,
  1304961,
  98554,
  2423810,
  1570229,
  302458,
  2806045,
  1534004,
  1463827,
  1085011,
  120989,
  1701753,
  110302,
  938429,
  1186733,
  2255246,
  425960,
  376311,
  341394,
  1061333,
  2025091,
  522270,
  598604,
  1000824,
  2254049,
  1857539,
  346425,
  1345187,
  550497,
  1251096,
  943720,
  681558,
  555972,
  779590,
  299796,
  1445763,
  459865,
  774572,
  489448,
  2407693,
  1574903,
  1630452,
  1907397,
  555045,
  1902494,
  1172223,
  142555,
  445864,
  1376151,
  1200389,
  327553,
  1548402,
  1106503,
  888650,
  41081,
  1245270,
  845610,
  1232215,
  387441,
  434475,
  1204003,
  1333189,
  1672468,
  567827,
  11392,
  631046,
  1299298,
  719608,
  714169,
  362247,
  1308257,
  530903,
  398202,
  885445,
  2606806,
  1354354,
  438760,
  194928,
  712863,
  1010340,
  2245646,
  376041,
  876890,
  1683404,
  955032,
  1065455,
  925034,
  1731713,
  1152271,
  2093865,
  1221433,
  629438,
  2054936,
  2643313,
  1322567,
  1492288,
  1844514,
  1802382,
  871,
  1350044,
  967406,
  756881,
  574442,
  1295864,
  1815978,
  2822668,
  2201377,
  2729436,
  616018,
  2318346,
  332717,
  289665,
  97812,
  1881483,
  1003188,
  702530,
  409314,
  645118,
  3645947,
  723792,
  503126,
  1609036,
  1647277,
  587437,
  735899,
  666552,
  27354,
  1045106,
  397951,
  1087090,
  1173872,
  1629962,
  1334261,
  1855668,
  2856970,
  1341188,
  336968,
  0,
  521349,
  53118,
  881926,
  154917,
  942966,
  1237636,
  820836,
  579583,
  1436861,
  2025006,
  634434,
  829152,
  298073,
  205380,
  1622350,
  1171051,
  848451,
  2417009,
  2016092,
  390510,
  2721874,
  359761,
  309038,
  1061522,
  297026,
  1311767,
  305305,
  854945,
  1773244,
  2656339,
  896058,
  1069160,
  1552917,
  1421821,
  440874,
  216699,
  1654864,
  521705,
  807422,
  1242602,
  1329872,
  308130,
  526463,
  27937,
  1450630,
  1621987,
  799154,
  1378289,
  2519996,
  1149046,
  579937,
  1841561,
  1895047,
  1009234,
  1922198,
  2570006,
  409696,
  442495,
  277484,
  979605,
  1392287,
  1023715,
  1881778,
  2432703,
  2297384,
  542451,
  1368100,
  833048,
  1038108,
  742376,
  1542317,
  2230186,
  1249077,
  884020,
  1286059,
  1102407,
  1651393,
  1787846,
  1370154,
  2734166,
  2935249,
  447485,
  736859,
  828966,
  1547038,
  765990,
  1427773,
  255456,
  134871,
  1597546,
  2173052,
  1187286,
  2364828,
  1220233,
  1760369,
  75080,
  2799969,
  1363310,
  2347168,
  272279,
  33698,
  1192053,
  342501,
  356092,
  136578,
  1701048,
  2216796,
  1340150,
  1852854,
  580862,
  407410,
  1860346,
  200649,
  954363,
  955621,
  2234154,
  2007706,
  646339,
  2712491,
  1259244,
  2368138,
  1550431,
  1160903,
  987838,
  650293,
  833228,
  368144,
  1998925,
  1733716,
  1050000,
  1061635,
  1144649,
  1260205,
  851043,
  1417512,
  2826918,
  1059350,
  1522135,
  1039943,
  703837,
  1035006,
  19505,
  211545,
  1461101,
  1238659,
  1414306,
  1151385,
  2169011,
  1101116,
  1118290,
  335296,
  1502266,
  1405699,
  1762457,
  530338,
  246108,
  484583,
  2164048,
  1614511,
  0,
  1446940,
  575450,
  2043329,
  2057251,
  774670,
  1084124
};