from array import array
rads=array('H', [11, 19, 59, 83, 107, 179, 227, 347, 419, 443, 467, 563, 587, 659, 1019, 1187, 1283, 1307, 1427, 1523, 1619, 1907] )
lrads=array('H', [5, 9, 29, 41, 53, 89, 113, 173, 209, 221, 233, 281, 293, 329, 509, 593, 641, 653, 713, 761, 809, 953] )
linvs= [1, 2, 20, 35, 36, 36, 78, 41, 74, 161, 228, 245L, 43L, 169L, 188L, 366L, 272L, 208L, 159L, 280L, 685L, 502L]
lcms= [1, 5, 45, 1305, 53505, 2835765, 252383085, 28519288605, 4933836928665, 1031171918090985, 227888993898107685, 53098135578259090605L, 14920576097490804460005L, 4371728796564805706781465L, 1438298774069821077531101985L, 732094076001538928463330910365L, 434131787068912584578755229846445L, 278278475511172966714982102331571245L, 181715844508795947264883312822516022985L, 129563397134771510399861802042453924388305L, 98597745219561119414294831354307436459500105L, 79765575882624945606164518565634716095735584945L]
rngs= [10, 90, 2610, 107010, 5671530, 504766170, 57038577210, 9867673857330, 2062343836181970, 455777987796215370, 106196271156518181210L, 29841152194981608920010L, 8743457593129611413562930L, 2876597548139642155062203970L, 1464188152003077856926661820730L, 868263574137825169157510459692890L, 556556951022345933429964204663142490L, 363431689017591894529766625645032045970L, 259126794269543020799723604084907848776610L, 197195490439122238828589662708614872919000210L, 159531151765249891212329037131269432191471169890L, 152033187632283146325349572386099768878472024905170L]
mxms= [1, 11, 209, 12331, 1023473, 109511611, 19602578369, 4449785289763, 1544075495547761, 646967632634511859, 286606661257088753537L, 133845310807060447901779L, 75354909984375032168701577L, 44233332160828143883027825699L, 29149765893985746818915337135641L, 29703611445971476008474728541218179L, 35258186786368142022059502778425978473L, 45236253646910326214302342064720530380859L, 59123783516511796362093161078589733207782713L, 84369639078062333408706940859147549287505931451L, 128494960315888933781460670928481717564871533599873L, 208033340751424183792184826233211900737527012898194387L]
logss= [array('H', [0, 0, 1, 8, 2, 4, 9, 7, 3, 6, 5]), array('H', [0, 0, 1, 13, 2, 16, 14, 6, 3, 8, 17, 12, 15, 5, 7, 11, 4, 10, 9]), array('H', [0, 0, 1, 50, 2, 6, 51, 18, 3, 42, 7, 25, 52, 45, 19, 56, 4, 40, 43, 38, 8, 10, 26, 15, 53, 12, 46, 34, 20, 28, 57, 49, 5, 17, 41, 24, 44, 55, 39, 37, 9, 14, 11, 33, 27, 48, 16, 23, 54, 36, 13, 32, 47, 22, 35, 31, 21, 30, 29]), array('H', [0, 0, 1, 72, 2, 27, 73, 8, 3, 62, 28, 24, 74, 77, 9, 17, 4, 56, 63, 47, 29, 80, 25, 60, 75, 54, 78, 52, 10, 12, 18, 38, 5, 14, 57, 35, 64, 20, 48, 67, 30, 40, 81, 71, 26, 7, 61, 23, 76, 16, 55, 46, 79, 59, 53, 51, 11, 37, 13, 34, 19, 66, 39, 70, 6, 22, 15, 45, 58, 50, 36, 33, 65, 69, 21, 44, 49, 32, 68, 43, 31, 42, 41]), array('H', [0, 0, 1, 70, 2, 47, 71, 43, 3, 34, 48, 22, 72, 14, 44, 11, 4, 29, 35, 78, 49, 7, 23, 62, 73, 94, 15, 104, 45, 32, 12, 27, 5, 92, 30, 90, 36, 38, 79, 84, 50, 40, 8, 59, 24, 81, 63, 66, 74, 86, 95, 99, 16, 52, 105, 69, 46, 42, 33, 21, 13, 10, 28, 77, 6, 61, 93, 103, 31, 26, 91, 89, 37, 83, 39, 58, 80, 65, 85, 98, 51, 68, 41, 20, 9, 76, 60, 102, 25, 88, 82, 57, 64, 97, 67, 19, 75, 101, 87, 56, 96, 18, 100, 55, 17, 54, 53]), array('H', [0, 0, 1, 108, 2, 138, 109, 171, 3, 38, 139, 15, 110, 114, 172, 68, 4, 166, 39, 54, 140, 101, 16, 135, 111, 98, 115, 146, 173, 118, 69, 62, 5, 123, 167, 131, 40, 149, 55, 44, 141, 155, 102, 80, 17, 176, 136, 36, 112, 164, 99, 96, 116, 121, 147, 153, 174, 162, 119, 160, 70, 72, 63, 31, 6, 74, 124, 86, 168, 65, 132, 59, 41, 33, 150, 28, 56, 8, 45, 11, 142, 76, 156, 24, 103, 126, 81, 48, 18, 88, 177, 107, 137, 170, 37, 14, 113, 67, 165, 53, 100, 134, 97, 145, 117, 61, 122, 130, 148, 43, 154, 79, 175, 35, 163, 95, 120, 152, 161, 159, 71, 30, 73, 85, 64, 58, 32, 27, 7, 10, 75, 23, 125, 47, 87, 106, 169, 13, 66, 52, 133, 144, 60, 129, 42, 78, 34, 94, 151, 158, 29, 84, 57, 26, 9, 22, 46, 105, 12, 51, 143, 128, 77, 93, 157, 83, 25, 21, 104, 50, 127, 92, 82, 20, 49, 91, 19, 90, 89]), array('H', [0, 0, 1, 46, 2, 11, 47, 154, 3, 92, 12, 28, 48, 61, 155, 57, 4, 99, 93, 178, 13, 200, 29, 34, 49, 22, 62, 138, 156, 8, 58, 197, 5, 74, 100, 165, 94, 77, 179, 107, 14, 131, 201, 150, 30, 103, 35, 218, 50, 82, 23, 145, 63, 168, 139, 39, 157, 224, 9, 90, 59, 97, 198, 20, 6, 72, 75, 129, 101, 80, 166, 222, 95, 70, 78, 68, 180, 182, 108, 192, 15, 184, 132, 209, 202, 110, 151, 54, 31, 194, 104, 215, 36, 17, 219, 189, 51, 186, 83, 120, 24, 134, 146, 86, 64, 211, 169, 173, 140, 204, 40, 123, 158, 112, 225, 45, 10, 153, 91, 27, 60, 56, 98, 177, 199, 33, 21, 137, 7, 196, 73, 164, 76, 106, 130, 149, 102, 217, 81, 144, 167, 38, 223, 89, 96, 19, 71, 128, 79, 221, 69, 67, 181, 191, 183, 208, 109, 53, 193, 214, 16, 188, 185, 119, 133, 85, 210, 172, 203, 122, 111, 44, 152, 26, 55, 176, 32, 136, 195, 163, 105, 148, 216, 143, 37, 88, 18, 127, 220, 66, 190, 207, 52, 213, 187, 118, 84, 171, 121, 43, 25, 175, 135, 162, 147, 142, 87, 126, 65, 206, 212, 117, 170, 42, 174, 161, 141, 125, 205, 116, 41, 160, 124, 115, 159, 114, 113]), array('H', [0, 0, 1, 152, 2, 277, 153, 289, 3, 304, 278, 272, 154, 238, 290, 83, 4, 183, 305, 145, 279, 95, 273, 91, 155, 208, 239, 110, 291, 192, 84, 54, 5, 78, 184, 220, 306, 159, 146, 44, 280, 315, 96, 322, 274, 235, 92, 189, 156, 232, 209, 335, 240, 212, 111, 203, 292, 297, 193, 136, 85, 338, 55, 247, 6, 169, 79, 50, 185, 243, 221, 72, 307, 28, 160, 14, 147, 215, 45, 225, 281, 262, 316, 254, 97, 114, 323, 344, 275, 302, 236, 181, 93, 206, 190, 76, 157, 313, 233, 230, 210, 295, 336, 167, 241, 26, 213, 260, 112, 300, 204, 311, 293, 24, 298, 22, 194, 196, 137, 126, 86, 198, 339, 121, 56, 139, 248, 32, 7, 128, 170, 286, 80, 88, 51, 41, 186, 200, 244, 69, 222, 341, 73, 164, 308, 123, 29, 38, 161, 58, 15, 61, 148, 141, 216, 331, 46, 250, 226, 18, 282, 34, 263, 267, 317, 9, 255, 64, 98, 130, 115, 103, 324, 172, 345, 151, 276, 288, 303, 271, 237, 82, 182, 144, 94, 90, 207, 109, 191, 53, 77, 219, 158, 43, 314, 321, 234, 188, 231, 334, 211, 202, 296, 135, 337, 246, 168, 49, 242, 71, 27, 13, 214, 224, 261, 253, 113, 343, 301, 180, 205, 75, 312, 229, 294, 166, 25, 259, 299, 310, 23, 21, 195, 125, 197, 120, 138, 31, 127, 285, 87, 40, 199, 68, 340, 163, 122, 37, 57, 60, 140, 330, 249, 17, 33, 266, 8, 63, 129, 102, 171, 150, 287, 270, 81, 143, 89, 108, 52, 218, 42, 320, 187, 333, 201, 134, 245, 48, 70, 12, 223, 252, 342, 179, 74, 228, 165, 258, 309, 20, 124, 119, 30, 284, 39, 67, 162, 36, 59, 329, 16, 265, 62, 101, 149, 269, 142, 107, 217, 319, 332, 133, 47, 11, 251, 178, 227, 257, 19, 118, 283, 66, 35, 328, 264, 100, 268, 106, 318, 132, 10, 177, 256, 117, 65, 327, 99, 105, 131, 176, 116, 326, 104, 175, 325, 174, 173]), array('H', [0, 0, 1, 100, 2, 272, 101, 44, 3, 200, 273, 287, 102, 304, 45, 372, 4, 393, 201, 339, 274, 144, 288, 280, 103, 126, 305, 300, 46, 50, 373, 327, 5, 387, 394, 316, 202, 24, 340, 404, 275, 136, 145, 14, 289, 54, 281, 220, 104, 88, 127, 75, 306, 269, 301, 141, 47, 21, 51, 266, 374, 377, 328, 244, 6, 158, 388, 83, 395, 380, 317, 361, 203, 238, 25, 226, 341, 331, 405, 40, 276, 400, 137, 357, 146, 247, 15, 150, 290, 33, 55, 348, 282, 9, 221, 193, 105, 116, 89, 69, 128, 161, 76, 251, 307, 416, 270, 198, 302, 391, 142, 124, 48, 385, 22, 134, 52, 86, 267, 19, 375, 156, 378, 236, 329, 398, 245, 31, 7, 114, 159, 414, 389, 383, 84, 154, 396, 112, 381, 110, 318, 320, 362, 173, 204, 322, 239, 188, 26, 364, 227, 294, 342, 175, 332, 181, 406, 206, 41, 369, 277, 324, 401, 217, 138, 241, 358, 37, 147, 190, 248, 121, 16, 28, 151, 170, 291, 366, 34, 167, 56, 229, 349, 59, 283, 296, 10, 262, 222, 344, 194, 232, 106, 177, 117, 258, 90, 334, 70, 352, 129, 183, 162, 94, 77, 408, 252, 62, 308, 208, 417, 99, 271, 43, 199, 286, 303, 371, 392, 338, 143, 279, 125, 299, 49, 326, 386, 315, 23, 403, 135, 13, 53, 219, 87, 74, 268, 140, 20, 265, 376, 243, 157, 82, 379, 360, 237, 225, 330, 39, 399, 356, 246, 149, 32, 347, 8, 192, 115, 68, 160, 250, 415, 197, 390, 123, 384, 133, 85, 18, 155, 235, 397, 30, 113, 413, 382, 153, 111, 109, 319, 172, 321, 187, 363, 293, 174, 180, 205, 368, 323, 216, 240, 36, 189, 120, 27, 169, 365, 166, 228, 58, 295, 261, 343, 231, 176, 257, 333, 351, 182, 93, 407, 61, 207, 98, 42, 285, 370, 337, 278, 298, 325, 314, 402, 12, 218, 73, 139, 264, 242, 81, 359, 224, 38, 355, 148, 346, 191, 67, 249, 196, 122, 132, 17, 234, 29, 412, 152, 108, 171, 186, 292, 179, 367, 215, 35, 119, 168, 165, 57, 260, 230, 256, 350, 92, 60, 97, 284, 336, 297, 313, 11, 72, 263, 80, 223, 354, 345, 66, 195, 131, 233, 411, 107, 185, 178, 214, 118, 164, 259, 255, 91, 96, 335, 312, 71, 79, 353, 65, 130, 410, 184, 213, 163, 254, 95, 311, 78, 64, 409, 212, 253, 310, 63, 211, 309, 210, 209]), array('H', [0, 0, 1, 318, 2, 241, 319, 235, 3, 194, 242, 295, 320, 286, 236, 117, 4, 376, 195, 407, 243, 111, 296, 133, 321, 40, 287, 70, 237, 107, 118, 179, 5, 171, 377, 34, 196, 122, 408, 162, 244, 150, 112, 265, 297, 435, 134, 270, 322, 28, 41, 252, 288, 183, 71, 94, 238, 283, 108, 104, 119, 432, 180, 429, 6, 85, 172, 52, 378, 9, 35, 278, 197, 143, 123, 358, 409, 88, 163, 302, 245, 388, 151, 217, 113, 175, 266, 425, 298, 202, 436, 79, 135, 55, 271, 206, 323, 313, 29, 47, 42, 381, 253, 398, 289, 352, 184, 336, 72, 12, 95, 440, 239, 192, 284, 374, 109, 38, 105, 169, 120, 148, 433, 26, 181, 281, 430, 83, 7, 141, 86, 386, 173, 200, 53, 311, 379, 350, 10, 190, 36, 146, 279, 139, 198, 348, 144, 346, 124, 126, 359, 366, 410, 128, 89, 420, 164, 361, 303, 59, 246, 368, 389, 258, 152, 412, 218, 232, 114, 130, 176, 159, 267, 91, 426, 275, 299, 422, 203, 395, 437, 166, 80, 308, 136, 363, 56, 229, 272, 305, 207, 210, 324, 61, 314, 403, 30, 248, 48, 213, 43, 370, 382, 342, 254, 391, 399, 327, 290, 260, 353, 331, 185, 154, 337, 64, 73, 414, 13, 19, 96, 220, 441, 317, 240, 234, 193, 294, 285, 116, 375, 406, 110, 132, 39, 69, 106, 178, 170, 33, 121, 161, 149, 264, 434, 269, 27, 251, 182, 93, 282, 103, 431, 428, 84, 51, 8, 277, 142, 357, 87, 301, 387, 216, 174, 424, 201, 78, 54, 205, 312, 46, 380, 397, 351, 335, 11, 439, 191, 373, 37, 168, 147, 25, 280, 82, 140, 385, 199, 310, 349, 189, 145, 138, 347, 345, 125, 365, 127, 419, 360, 58, 367, 257, 411, 231, 129, 158, 90, 274, 421, 394, 165, 307, 362, 228, 304, 209, 60, 402, 247, 212, 369, 341, 390, 326, 259, 330, 153, 63, 413, 18, 219, 316, 233, 293, 115, 405, 131, 68, 177, 32, 160, 263, 268, 250, 92, 102, 427, 50, 276, 356, 300, 215, 423, 77, 204, 45, 396, 334, 438, 372, 167, 24, 81, 384, 309, 188, 137, 344, 364, 418, 57, 256, 230, 157, 273, 393, 306, 227, 208, 401, 211, 340, 325, 329, 62, 17, 315, 292, 404, 67, 31, 262, 249, 101, 49, 355, 214, 76, 44, 333, 371, 23, 383, 187, 343, 417, 255, 156, 392, 226, 400, 339, 328, 16, 291, 66, 261, 100, 354, 75, 332, 22, 186, 416, 155, 225, 338, 15, 65, 99, 74, 21, 415, 224, 14, 98, 20, 223, 97, 222, 221]), array('H', [0, 0, 1, 450, 2, 41, 451, 148, 3, 434, 42, 141, 452, 30, 149, 25, 4, 284, 435, 387, 43, 132, 142, 338, 453, 82, 31, 418, 150, 213, 26, 209, 5, 125, 285, 189, 436, 119, 388, 14, 44, 96, 133, 310, 143, 9, 339, 408, 454, 296, 83, 268, 32, 74, 419, 182, 151, 371, 214, 38, 27, 129, 210, 116, 6, 71, 126, 319, 286, 322, 190, 344, 437, 461, 120, 66, 389, 289, 15, 163, 45, 402, 97, 224, 134, 325, 311, 197, 144, 334, 10, 178, 340, 193, 409, 428, 455, 394, 297, 109, 84, 347, 269, 413, 33, 173, 75, 245, 420, 440, 183, 103, 152, 256, 372, 379, 215, 464, 39, 432, 28, 282, 130, 80, 211, 123, 117, 94, 7, 294, 72, 369, 127, 69, 320, 459, 287, 400, 323, 332, 191, 392, 345, 171, 438, 254, 462, 280, 121, 292, 67, 398, 390, 252, 290, 250, 16, 18, 164, 58, 46, 20, 403, 158, 98, 166, 225, 301, 135, 60, 326, 355, 312, 48, 198, 230, 145, 22, 335, 206, 11, 405, 179, 113, 341, 160, 194, 425, 410, 100, 429, 91, 456, 168, 395, 55, 298, 227, 110, 88, 85, 303, 348, 361, 270, 137, 414, 306, 34, 62, 174, 241, 76, 328, 246, 351, 421, 357, 441, 445, 184, 314, 104, 364, 153, 50, 257, 262, 373, 200, 380, 273, 216, 232, 465, 449, 40, 147, 433, 140, 29, 24, 283, 386, 131, 337, 81, 417, 212, 208, 124, 188, 118, 13, 95, 309, 8, 407, 295, 267, 73, 181, 370, 37, 128, 115, 70, 318, 321, 343, 460, 65, 288, 162, 401, 223, 324, 196, 333, 177, 192, 427, 393, 108, 346, 412, 172, 244, 439, 102, 255, 378, 463, 431, 281, 79, 122, 93, 293, 368, 68, 458, 399, 331, 391, 170, 253, 279, 291, 397, 251, 249, 17, 57, 19, 157, 165, 300, 59, 354, 47, 229, 21, 205, 404, 112, 159, 424, 99, 90, 167, 54, 226, 87, 302, 360, 136, 305, 61, 240, 327, 350, 356, 444, 313, 363, 49, 261, 199, 272, 231, 448, 146, 139, 23, 385, 336, 416, 207, 187, 12, 308, 406, 266, 180, 36, 114, 317, 342, 64, 161, 222, 195, 176, 426, 107, 411, 243, 101, 377, 430, 78, 92, 367, 457, 330, 169, 278, 396, 248, 56, 156, 299, 353, 228, 204, 111, 423, 89, 53, 86, 359, 304, 239, 349, 443, 362, 260, 271, 447, 138, 384, 415, 186, 307, 265, 35, 316, 63, 221, 175, 106, 242, 376, 77, 366, 329, 277, 247, 155, 352, 203, 422, 52, 358, 238, 442, 259, 446, 383, 185, 264, 315, 220, 105, 375, 365, 276, 154, 202, 51, 237, 258, 382, 263, 219, 374, 275, 201, 236, 381, 218, 274, 235, 217, 234, 233]), array('H', [0, 0, 1, 530, 2, 115, 531, 130, 3, 498, 116, 554, 532, 504, 131, 83, 4, 322, 499, 46, 117, 98, 555, 302, 533, 230, 505, 466, 132, 205, 84, 459, 5, 522, 323, 245, 500, 201, 47, 472, 118, 423, 99, 341, 556, 51, 303, 30, 534, 260, 231, 290, 506, 125, 467, 107, 133, 14, 206, 350, 85, 476, 460, 66, 6, 57, 523, 182, 324, 270, 246, 112, 501, 95, 202, 198, 48, 122, 473, 267, 119, 434, 424, 369, 100, 437, 342, 173, 557, 517, 52, 72, 304, 427, 31, 161, 535, 77, 261, 490, 232, 372, 291, 138, 507, 213, 126, 298, 468, 103, 108, 169, 134, 448, 15, 417, 207, 440, 351, 452, 86, 546, 477, 391, 461, 345, 67, 386, 7, 309, 58, 189, 524, 176, 183, 19, 325, 362, 271, 409, 247, 560, 113, 496, 502, 320, 96, 228, 203, 520, 199, 421, 49, 258, 123, 12, 474, 55, 268, 93, 120, 432, 435, 515, 425, 75, 370, 211, 101, 446, 438, 544, 343, 307, 174, 360, 558, 318, 518, 256, 53, 430, 73, 444, 305, 316, 428, 314, 32, 34, 162, 148, 536, 36, 78, 25, 262, 164, 491, 355, 233, 150, 373, 335, 292, 538, 139, 238, 508, 38, 214, 278, 127, 80, 299, 456, 469, 27, 104, 63, 109, 264, 170, 158, 135, 166, 449, 383, 16, 493, 418, 90, 208, 357, 441, 145, 352, 235, 453, 155, 87, 152, 547, 402, 478, 375, 392, 550, 462, 337, 346, 194, 68, 294, 387, 405, 8, 540, 310, 331, 59, 141, 190, 481, 525, 240, 177, 485, 184, 510, 20, 378, 326, 40, 363, 222, 272, 216, 410, 395, 248, 280, 561, 529, 114, 129, 497, 553, 503, 82, 321, 45, 97, 301, 229, 465, 204, 458, 521, 244, 200, 471, 422, 340, 50, 29, 259, 289, 124, 106, 13, 349, 475, 65, 56, 181, 269, 111, 94, 197, 121, 266, 433, 368, 436, 172, 516, 71, 426, 160, 76, 489, 371, 137, 212, 297, 102, 168, 447, 416, 439, 451, 545, 390, 344, 385, 308, 188, 175, 18, 361, 408, 559, 495, 319, 227, 519, 420, 257, 11, 54, 92, 431, 514, 74, 210, 445, 543, 306, 359, 317, 255, 429, 443, 315, 313, 33, 147, 35, 24, 163, 354, 149, 334, 537, 237, 37, 277, 79, 455, 26, 62, 263, 157, 165, 382, 492, 89, 356, 144, 234, 154, 151, 401, 374, 549, 336, 193, 293, 404, 539, 330, 140, 480, 239, 484, 509, 377, 39, 221, 215, 394, 279, 528, 128, 552, 81, 44, 300, 464, 457, 243, 470, 339, 28, 288, 105, 348, 64, 180, 110, 196, 265, 367, 171, 70, 159, 488, 136, 296, 167, 415, 450, 389, 384, 187, 17, 407, 494, 226, 419, 10, 91, 513, 209, 542, 358, 254, 442, 312, 146, 23, 353, 333, 236, 276, 454, 61, 156, 381, 88, 143, 153, 400, 548, 192, 403, 329, 479, 483, 376, 220, 393, 527, 551, 43, 463, 242, 338, 287, 347, 179, 195, 366, 69, 487, 295, 414, 388, 186, 406, 225, 9, 512, 541, 253, 311, 22, 332, 275, 60, 380, 142, 399, 191, 328, 482, 219, 526, 42, 241, 286, 178, 365, 486, 413, 185, 224, 511, 252, 21, 274, 379, 398, 327, 218, 41, 285, 364, 412, 223, 251, 273, 397, 217, 284, 411, 250, 396, 283, 249, 282, 281]), array('H', [0, 0, 1, 478, 2, 205, 479, 346, 3, 370, 206, 83, 480, 305, 347, 97, 4, 38, 371, 233, 207, 238, 84, 363, 481, 410, 306, 262, 348, 432, 98, 354, 5, 561, 39, 551, 372, 201, 234, 197, 208, 251, 239, 336, 85, 575, 364, 176, 482, 106, 411, 516, 307, 212, 263, 288, 349, 125, 433, 272, 99, 157, 355, 130, 6, 510, 562, 220, 40, 255, 552, 523, 373, 182, 202, 302, 235, 429, 198, 572, 209, 154, 252, 426, 240, 243, 337, 324, 86, 26, 576, 65, 365, 246, 177, 438, 483, 19, 107, 453, 412, 340, 517, 461, 308, 443, 213, 395, 264, 327, 289, 93, 350, 172, 126, 568, 434, 89, 273, 384, 100, 166, 158, 143, 356, 29, 131, 277, 7, 228, 511, 421, 563, 579, 221, 467, 41, 488, 256, 59, 553, 68, 524, 388, 374, 51, 183, 584, 203, 368, 303, 36, 236, 408, 430, 559, 199, 249, 573, 104, 210, 123, 155, 508, 253, 180, 427, 152, 241, 24, 244, 17, 338, 441, 325, 170, 87, 164, 27, 226, 577, 486, 66, 49, 366, 406, 247, 121, 178, 22, 439, 162, 484, 404, 20, 402, 108, 110, 454, 314, 413, 112, 341, 192, 518, 456, 462, 147, 309, 316, 444, 472, 214, 415, 396, 541, 265, 114, 328, 74, 290, 343, 94, 360, 351, 194, 173, 285, 127, 520, 569, 321, 435, 458, 90, 381, 274, 464, 385, 33, 101, 149, 167, 46, 159, 311, 144, 538, 357, 318, 30, 535, 132, 446, 278, 135, 8, 474, 229, 547, 512, 216, 422, 449, 564, 417, 580, 504, 222, 398, 468, 281, 42, 543, 489, 493, 257, 267, 60, 138, 554, 116, 69, 530, 525, 330, 389, 11, 375, 76, 52, 497, 184, 292, 585, 477, 204, 345, 369, 82, 304, 96, 37, 232, 237, 362, 409, 261, 431, 353, 560, 550, 200, 196, 250, 335, 574, 175, 105, 515, 211, 287, 124, 271, 156, 129, 509, 219, 254, 522, 181, 301, 428, 571, 153, 425, 242, 323, 25, 64, 245, 437, 18, 452, 339, 460, 442, 394, 326, 92, 171, 567, 88, 383, 165, 142, 28, 276, 227, 420, 578, 466, 487, 58, 67, 387, 50, 583, 367, 35, 407, 558, 248, 103, 122, 507, 179, 151, 23, 16, 440, 169, 163, 225, 485, 48, 405, 120, 21, 161, 403, 401, 109, 313, 111, 191, 455, 146, 315, 471, 414, 540, 113, 73, 342, 359, 193, 284, 519, 320, 457, 380, 463, 32, 148, 45, 310, 537, 317, 534, 445, 134, 473, 546, 215, 448, 416, 503, 397, 280, 542, 492, 266, 137, 115, 529, 329, 10, 75, 496, 291, 476, 344, 81, 95, 231, 361, 260, 352, 549, 195, 334, 174, 514, 286, 270, 128, 218, 521, 300, 570, 424, 322, 63, 436, 451, 459, 393, 91, 566, 382, 141, 275, 419, 465, 57, 386, 582, 34, 557, 102, 506, 150, 15, 168, 224, 47, 119, 160, 400, 312, 190, 145, 470, 539, 72, 358, 283, 319, 379, 31, 44, 536, 533, 133, 545, 447, 502, 279, 491, 136, 528, 9, 495, 475, 80, 230, 259, 548, 333, 513, 269, 217, 299, 423, 62, 450, 392, 565, 140, 418, 56, 581, 556, 505, 14, 223, 118, 399, 189, 469, 71, 282, 378, 43, 532, 544, 501, 490, 527, 494, 79, 258, 332, 268, 298, 61, 391, 139, 55, 555, 13, 117, 188, 70, 377, 531, 500, 526, 78, 331, 297, 390, 54, 12, 187, 376, 499, 77, 296, 53, 186, 498, 295, 185, 294, 293]), array('H', [0, 0, 1, 186, 2, 52, 187, 405, 3, 372, 53, 418, 188, 596, 406, 238, 4, 536, 373, 388, 54, 591, 419, 160, 189, 104, 597, 558, 407, 501, 239, 399, 5, 604, 537, 457, 374, 32, 389, 124, 55, 511, 592, 497, 420, 424, 161, 581, 190, 152, 105, 64, 598, 301, 559, 470, 408, 574, 502, 622, 240, 428, 400, 119, 6, 648, 605, 365, 538, 346, 458, 11, 375, 616, 33, 290, 390, 165, 125, 226, 56, 86, 512, 49, 593, 588, 498, 29, 421, 298, 425, 343, 162, 585, 582, 440, 191, 307, 153, 132, 106, 443, 65, 653, 599, 643, 302, 20, 560, 194, 471, 218, 409, 201, 575, 212, 503, 310, 623, 283, 241, 178, 429, 39, 401, 156, 120, 466, 7, 25, 649, 279, 606, 135, 366, 610, 539, 545, 347, 322, 459, 109, 12, 356, 376, 553, 617, 338, 34, 446, 291, 139, 391, 250, 166, 451, 126, 68, 227, 487, 57, 565, 87, 74, 513, 656, 50, 370, 594, 534, 589, 102, 499, 602, 30, 509, 422, 150, 299, 572, 426, 646, 344, 614, 163, 84, 586, 296, 583, 305, 441, 641, 192, 199, 308, 176, 154, 23, 133, 543, 107, 551, 444, 248, 66, 563, 654, 532, 600, 148, 644, 82, 303, 197, 21, 549, 561, 146, 195, 144, 472, 474, 219, 525, 410, 476, 202, 233, 576, 221, 213, 351, 504, 527, 311, 633, 624, 412, 284, 316, 242, 478, 179, 272, 430, 204, 40, 326, 402, 235, 157, 396, 121, 578, 467, 116, 8, 223, 26, 437, 650, 215, 280, 463, 607, 353, 136, 484, 367, 506, 611, 638, 540, 529, 546, 522, 348, 313, 323, 113, 460, 635, 110, 255, 13, 626, 357, 258, 377, 414, 554, 493, 618, 286, 339, 16, 35, 318, 447, 98, 292, 244, 140, 629, 392, 480, 251, 94, 167, 181, 452, 360, 127, 274, 69, 171, 228, 432, 488, 261, 58, 206, 566, 266, 88, 42, 75, 380, 514, 328, 657, 185, 51, 404, 371, 417, 595, 237, 535, 387, 590, 159, 103, 557, 500, 398, 603, 456, 31, 123, 510, 496, 423, 580, 151, 63, 300, 469, 573, 621, 427, 118, 647, 364, 345, 10, 615, 289, 164, 225, 85, 48, 587, 28, 297, 342, 584, 439, 306, 131, 442, 652, 642, 19, 193, 217, 200, 211, 309, 282, 177, 38, 155, 465, 24, 278, 134, 609, 544, 321, 108, 355, 552, 337, 445, 138, 249, 450, 67, 486, 564, 73, 655, 369, 533, 101, 601, 508, 149, 571, 645, 613, 83, 295, 304, 640, 198, 175, 22, 542, 550, 247, 562, 531, 147, 81, 196, 548, 145, 143, 473, 524, 475, 232, 220, 350, 526, 632, 411, 315, 477, 271, 203, 325, 234, 395, 577, 115, 222, 436, 214, 462, 352, 483, 505, 637, 528, 521, 312, 112, 634, 254, 625, 257, 413, 492, 285, 15, 317, 97, 243, 628, 479, 93, 180, 359, 273, 170, 431, 260, 205, 265, 41, 379, 327, 184, 403, 416, 236, 386, 158, 556, 397, 455, 122, 495, 579, 62, 468, 620, 117, 363, 9, 288, 224, 47, 27, 341, 438, 130, 651, 18, 216, 210, 281, 37, 464, 277, 608, 320, 354, 336, 137, 449, 485, 72, 368, 100, 507, 570, 612, 294, 639, 174, 541, 246, 530, 80, 547, 142, 523, 231, 349, 631, 314, 270, 324, 394, 114, 435, 461, 482, 636, 520, 111, 253, 256, 491, 14, 96, 627, 92, 358, 169, 259, 264, 378, 183, 415, 385, 555, 454, 494, 61, 619, 362, 287, 46, 340, 129, 17, 209, 36, 276, 319, 335, 448, 71, 99, 569, 293, 173, 245, 79, 141, 230, 630, 269, 393, 434, 481, 519, 252, 490, 95, 91, 168, 263, 182, 384, 453, 60, 361, 45, 128, 208, 275, 334, 70, 568, 172, 78, 229, 268, 433, 518, 489, 90, 262, 383, 59, 44, 207, 333, 567, 77, 267, 517, 89, 382, 43, 332, 76, 516, 381, 331, 515, 330, 329]), array('H', [0, 0, 1, 958, 2, 10, 959, 363, 3, 898, 11, 756, 960, 289, 364, 968, 4, 48, 899, 542, 12, 303, 757, 114, 961, 20, 290, 838, 365, 138, 969, 324, 5, 696, 49, 373, 900, 701, 543, 229, 13, 939, 304, 346, 758, 908, 115, 211, 962, 726, 21, 1006, 291, 927, 839, 766, 366, 482, 139, 465, 970, 851, 325, 243, 6, 299, 697, 923, 50, 54, 374, 165, 901, 594, 702, 978, 544, 101, 230, 732, 14, 778, 940, 681, 305, 58, 347, 78, 759, 784, 909, 652, 116, 264, 212, 552, 963, 206, 727, 636, 22, 378, 1007, 745, 292, 313, 928, 995, 840, 154, 767, 641, 367, 630, 483, 124, 140, 169, 466, 411, 971, 494, 852, 879, 326, 30, 244, 446, 7, 286, 300, 135, 698, 905, 924, 848, 51, 98, 55, 261, 375, 151, 166, 27, 902, 148, 595, 666, 703, 598, 979, 180, 545, 946, 102, 334, 231, 669, 733, 867, 15, 477, 779, 489, 941, 706, 682, 616, 306, 578, 59, 422, 348, 601, 79, 383, 760, 405, 785, 825, 910, 982, 653, 791, 117, 711, 265, 804, 213, 183, 553, 505, 964, 320, 207, 239, 728, 548, 637, 442, 23, 863, 379, 501, 1008, 949, 746, 1012, 293, 280, 314, 890, 929, 105, 996, 356, 841, 687, 155, 534, 768, 337, 642, 953, 368, 918, 631, 130, 484, 234, 125, 41, 141, 585, 170, 221, 467, 672, 412, 750, 972, 255, 495, 718, 853, 736, 880, 831, 327, 621, 31, 457, 245, 870, 447, 1016, 8, 896, 287, 46, 301, 18, 136, 694, 699, 937, 906, 724, 925, 480, 849, 297, 52, 592, 99, 776, 56, 782, 262, 204, 376, 311, 152, 628, 167, 492, 28, 284, 903, 96, 149, 146, 596, 944, 667, 475, 704, 576, 599, 403, 980, 709, 181, 318, 546, 861, 947, 278, 103, 685, 335, 916, 232, 583, 670, 253, 734, 619, 868, 894, 16, 935, 478, 590, 780, 309, 490, 94, 942, 574, 707, 859, 683, 581, 617, 933, 307, 572, 579, 570, 60, 62, 423, 71, 349, 64, 602, 817, 80, 425, 384, 109, 761, 73, 406, 175, 786, 351, 826, 199, 911, 66, 983, 434, 654, 604, 792, 1000, 118, 819, 712, 272, 266, 82, 805, 988, 214, 427, 184, 526, 554, 386, 506, 360, 965, 111, 321, 226, 208, 763, 240, 162, 729, 75, 549, 742, 638, 408, 443, 845, 24, 177, 864, 613, 380, 788, 502, 439, 1009, 353, 950, 38, 747, 828, 1013, 691, 294, 201, 281, 472, 315, 913, 891, 91, 930, 68, 106, 196, 997, 985, 357, 159, 842, 436, 688, 88, 156, 656, 535, 659, 769, 606, 338, 395, 643, 794, 954, 538, 369, 1002, 919, 677, 632, 120, 131, 662, 485, 821, 235, 886, 126, 714, 42, 772, 142, 274, 586, 566, 171, 268, 222, 609, 468, 84, 673, 562, 413, 807, 751, 341, 973, 990, 256, 417, 496, 216, 719, 398, 854, 429, 737, 191, 881, 186, 832, 646, 328, 528, 622, 811, 32, 556, 458, 797, 246, 388, 871, 518, 448, 508, 1017, 957, 9, 362, 897, 755, 288, 967, 47, 541, 302, 113, 19, 837, 137, 323, 695, 372, 700, 228, 938, 345, 907, 210, 725, 1005, 926, 765, 481, 464, 850, 242, 298, 922, 53, 164, 593, 977, 100, 731, 777, 680, 57, 77, 783, 651, 263, 551, 205, 635, 377, 744, 312, 994, 153, 640, 629, 123, 168, 410, 493, 878, 29, 445, 285, 134, 904, 847, 97, 260, 150, 26, 147, 665, 597, 179, 945, 333, 668, 866, 476, 488, 705, 615, 577, 421, 600, 382, 404, 824, 981, 790, 710, 803, 182, 504, 319, 238, 547, 441, 862, 500, 948, 1011, 279, 889, 104, 355, 686, 533, 336, 952, 917, 129, 233, 40, 584, 220, 671, 749, 254, 717, 735, 830, 620, 456, 869, 1015, 895, 45, 17, 693, 936, 723, 479, 296, 591, 775, 781, 203, 310, 627, 491, 283, 95, 145, 943, 474, 575, 402, 708, 317, 860, 277, 684, 915, 582, 252, 618, 893, 934, 589, 308, 93, 573, 858, 580, 932, 571, 569, 61, 70, 63, 816, 424, 108, 72, 174, 350, 198, 65, 433, 603, 999, 818, 271, 81, 987, 426, 525, 385, 359, 110, 225, 762, 161, 74, 741, 407, 844, 176, 612, 787, 438, 352, 37, 827, 690, 200, 471, 912, 90, 67, 195, 984, 158, 435, 87, 655, 658, 605, 394, 793, 537, 1001, 676, 119, 661, 820, 885, 713, 771, 273, 565, 267, 608, 83, 561, 806, 340, 989, 416, 215, 397, 428, 190, 185, 645, 527, 810, 555, 796, 387, 517, 507, 956, 361, 754, 966, 540, 112, 836, 322, 371, 227, 344, 209, 1004, 764, 463, 241, 921, 163, 976, 730, 679, 76, 650, 550, 634, 743, 993, 639, 122, 409, 877, 444, 133, 846, 259, 25, 664, 178, 332, 865, 487, 614, 420, 381, 823, 789, 802, 503, 237, 440, 499, 1010, 888, 354, 532, 951, 128, 39, 219, 748, 716, 829, 455, 1014, 44, 692, 722, 295, 774, 202, 626, 282, 144, 473, 401, 316, 276, 914, 251, 892, 588, 92, 857, 931, 568, 69, 815, 107, 173, 197, 432, 998, 270, 986, 524, 358, 224, 160, 740, 843, 611, 437, 36, 689, 470, 89, 194, 157, 86, 657, 393, 536, 675, 660, 884, 770, 564, 607, 560, 339, 415, 396, 189, 644, 809, 795, 516, 955, 753, 539, 835, 370, 343, 1003, 462, 920, 975, 678, 649, 633, 992, 121, 876, 132, 258, 663, 331, 486, 419, 822, 801, 236, 498, 887, 531, 127, 218, 715, 454, 43, 721, 773, 625, 143, 400, 275, 250, 587, 856, 567, 814, 172, 431, 269, 523, 223, 739, 610, 35, 469, 193, 85, 392, 674, 883, 563, 559, 414, 188, 808, 515, 752, 834, 342, 461, 974, 648, 991, 875, 257, 330, 418, 800, 497, 530, 217, 453, 720, 624, 399, 249, 855, 813, 430, 522, 738, 34, 192, 391, 882, 558, 187, 514, 833, 460, 647, 874, 329, 799, 529, 452, 623, 248, 812, 521, 33, 390, 557, 513, 459, 873, 798, 451, 247, 520, 389, 512, 872, 450, 519, 511, 449, 510, 509]), array('H', [0, 0, 1, 646, 2, 1111, 647, 781, 3, 106, 1112, 432, 648, 500, 782, 571, 4, 1125, 107, 225, 1113, 241, 433, 790, 649, 1036, 501, 752, 783, 231, 572, 473, 5, 1078, 1126, 706, 108, 48, 226, 1146, 1114, 956, 242, 342, 434, 31, 791, 205, 650, 376, 1037, 585, 502, 401, 753, 357, 784, 871, 232, 261, 573, 1151, 474, 887, 6, 425, 1079, 118, 1127, 250, 707, 1174, 109, 814, 49, 496, 227, 27, 1147, 23, 1115, 212, 957, 847, 243, 1050, 343, 877, 435, 665, 32, 95, 792, 1119, 206, 150, 651, 735, 377, 538, 1038, 388, 586, 914, 503, 166, 402, 87, 754, 216, 358, 694, 785, 352, 872, 715, 233, 606, 262, 720, 574, 864, 1152, 416, 475, 961, 888, 921, 7, 988, 426, 490, 1080, 1006, 119, 677, 1128, 685, 251, 1086, 708, 851, 1175, 932, 110, 156, 815, 1022, 50, 1108, 497, 238, 228, 45, 28, 398, 1148, 247, 24, 1047, 1116, 385, 213, 603, 958, 1003, 848, 1105, 244, 1000, 1051, 331, 344, 1054, 878, 631, 436, 907, 666, 298, 33, 334, 96, 611, 793, 1159, 1120, 371, 207, 347, 151, 902, 652, 177, 736, 1071, 378, 1057, 539, 134, 1039, 764, 389, 1012, 587, 881, 915, 896, 504, 657, 167, 562, 403, 634, 88, 267, 755, 68, 217, 274, 359, 439, 695, 777, 786, 1142, 353, 1170, 873, 910, 716, 673, 234, 1101, 607, 130, 263, 669, 721, 78, 575, 182, 865, 858, 1153, 301, 417, 725, 476, 307, 962, 16, 889, 36, 922, 510, 8, 452, 989, 829, 427, 337, 491, 82, 1081, 326, 1007, 125, 120, 99, 678, 319, 1129, 741, 686, 282, 252, 614, 1087, 579, 709, 292, 852, 948, 1176, 796, 933, 551, 111, 1064, 157, 195, 816, 1162, 1023, 186, 51, 1184, 1109, 104, 498, 1123, 239, 1034, 229, 1076, 46, 954, 29, 374, 399, 869, 1149, 423, 248, 812, 25, 210, 1048, 663, 1117, 733, 386, 164, 214, 350, 604, 862, 959, 986, 1004, 683, 849, 154, 1106, 43, 245, 383, 1001, 998, 1052, 905, 332, 1157, 345, 175, 1055, 762, 879, 655, 632, 66, 437, 1140, 908, 1099, 667, 180, 299, 305, 34, 450, 335, 324, 97, 739, 612, 290, 794, 1062, 1160, 1182, 1121, 1074, 372, 421, 208, 731, 348, 984, 152, 381, 903, 173, 653, 1138, 178, 448, 737, 1060, 1072, 729, 379, 1136, 1058, 1134, 540, 542, 135, 466, 1040, 544, 765, 973, 390, 137, 1013, 480, 588, 468, 882, 145, 916, 1042, 897, 772, 505, 546, 658, 61, 168, 767, 563, 311, 404, 975, 635, 746, 89, 392, 268, 942, 756, 139, 69, 802, 218, 1015, 275, 966, 360, 482, 440, 529, 696, 590, 778, 568, 787, 470, 1143, 202, 354, 884, 1171, 20, 874, 147, 911, 691, 717, 918, 674, 929, 235, 1044, 1102, 628, 608, 899, 131, 893, 264, 774, 670, 75, 722, 507, 79, 316, 576, 548, 183, 1031, 866, 660, 859, 40, 1154, 63, 302, 287, 418, 170, 726, 463, 477, 769, 308, 939, 963, 565, 17, 926, 890, 313, 37, 460, 923, 406, 511, 409, 9, 977, 453, 839, 990, 637, 830, 514, 428, 748, 338, 257, 492, 91, 83, 412, 1082, 394, 327, 367, 1008, 270, 126, 12, 121, 944, 100, 808, 679, 758, 320, 980, 1130, 141, 742, 525, 687, 71, 283, 456, 253, 804, 615, 619, 1088, 220, 580, 842, 710, 1017, 293, 557, 853, 277, 949, 993, 1177, 968, 797, 623, 934, 362, 552, 640, 112, 484, 1065, 823, 158, 442, 196, 833, 817, 531, 1163, 1092, 1024, 698, 187, 517, 52, 592, 1185, 645, 1110, 780, 105, 431, 499, 570, 1124, 224, 240, 789, 1035, 751, 230, 472, 1077, 705, 47, 1145, 955, 341, 30, 204, 375, 584, 400, 356, 870, 260, 1150, 886, 424, 117, 249, 1173, 813, 495, 26, 22, 211, 846, 1049, 876, 664, 94, 1118, 149, 734, 537, 387, 913, 165, 86, 215, 693, 351, 714, 605, 719, 863, 415, 960, 920, 987, 489, 1005, 676, 684, 1085, 850, 931, 155, 1021, 1107, 237, 44, 397, 246, 1046, 384, 602, 1002, 1104, 999, 330, 1053, 630, 906, 297, 333, 610, 1158, 370, 346, 901, 176, 1070, 1056, 133, 763, 1011, 880, 895, 656, 561, 633, 266, 67, 273, 438, 776, 1141, 1169, 909, 672, 1100, 129, 668, 77, 181, 857, 300, 724, 306, 15, 35, 509, 451, 828, 336, 81, 325, 124, 98, 318, 740, 281, 613, 578, 291, 947, 795, 550, 1063, 194, 1161, 185, 1183, 103, 1122, 1033, 1075, 953, 373, 868, 422, 811, 209, 662, 732, 163, 349, 861, 985, 682, 153, 42, 382, 997, 904, 1156, 174, 761, 654, 65, 1139, 1098, 179, 304, 449, 323, 738, 289, 1061, 1181, 1073, 420, 730, 983, 380, 172, 1137, 447, 1059, 728, 1135, 1133, 541, 465, 543, 972, 136, 479, 467, 144, 1041, 771, 545, 60, 766, 310, 974, 745, 391, 941, 138, 801, 1014, 965, 481, 528, 589, 567, 469, 201, 883, 19, 146, 690, 917, 928, 1043, 627, 898, 892, 773, 74, 506, 315, 547, 1030, 659, 39, 62, 286, 169, 462, 768, 938, 564, 925, 312, 459, 405, 408, 976, 838, 636, 513, 747, 256, 90, 411, 393, 366, 269, 11, 943, 807, 757, 979, 140, 524, 70, 455, 803, 618, 219, 841, 1016, 556, 276, 992, 967, 622, 361, 639, 483, 822, 441, 832, 530, 1091, 697, 516, 591, 644, 779, 430, 569, 223, 788, 750, 471, 704, 1144, 340, 203, 583, 355, 259, 885, 116, 1172, 494, 21, 845, 875, 93, 148, 536, 912, 85, 692, 713, 718, 414, 919, 488, 675, 1084, 930, 1020, 236, 396, 1045, 601, 1103, 329, 629, 296, 609, 369, 900, 1069, 132, 1010, 894, 560, 265, 272, 775, 1168, 671, 128, 76, 856, 723, 14, 508, 827, 80, 123, 317, 280, 577, 946, 549, 193, 184, 102, 1032, 952, 867, 810, 661, 162, 860, 681, 41, 996, 1155, 760, 64, 1097, 303, 322, 288, 1180, 419, 982, 171, 446, 727, 1132, 464, 971, 478, 143, 770, 59, 309, 744, 940, 800, 964, 527, 566, 200, 18, 689, 927, 626, 891, 73, 314, 1029, 38, 285, 461, 937, 924, 458, 407, 837, 512, 255, 410, 365, 10, 806, 978, 523, 454, 617, 840, 555, 991, 621, 638, 821, 831, 1090, 515, 643, 429, 222, 749, 703, 339, 582, 258, 115, 493, 844, 92, 535, 84, 712, 413, 487, 1083, 1019, 395, 600, 328, 295, 368, 1068, 1009, 559, 271, 1167, 127, 855, 13, 826, 122, 279, 945, 192, 101, 951, 809, 161, 680, 995, 759, 1096, 321, 1179, 981, 445, 1131, 970, 142, 58, 743, 799, 526, 199, 688, 625, 72, 1028, 284, 936, 457, 836, 254, 364, 805, 522, 616, 554, 620, 820, 1089, 642, 221, 702, 581, 114, 843, 534, 711, 486, 1018, 599, 294, 1067, 558, 1166, 854, 825, 278, 191, 950, 160, 994, 1095, 1178, 444, 969, 57, 798, 198, 624, 1027, 935, 835, 363, 521, 553, 819, 641, 701, 113, 533, 485, 598, 1066, 1165, 824, 190, 159, 1094, 443, 56, 197, 1026, 834, 520, 818, 700, 532, 597, 1164, 189, 1093, 55, 1025, 519, 699, 596, 188, 54, 518, 595, 53, 594, 593]), array('H', [0, 0, 1, 1214, 2, 565, 1215, 1027, 3, 1146, 566, 406, 1216, 1014, 1028, 497, 4, 864, 1147, 280, 567, 959, 407, 817, 1217, 1130, 1015, 1078, 1029, 1260, 498, 602, 5, 338, 865, 310, 1148, 906, 281, 946, 568, 1255, 960, 529, 408, 429, 818, 591, 1218, 772, 1131, 796, 1016, 1112, 1079, 971, 1030, 212, 1261, 90, 499, 965, 603, 891, 6, 297, 339, 927, 866, 749, 311, 59, 1149, 737, 907, 1062, 282, 151, 947, 917, 569, 1010, 1256, 425, 961, 147, 530, 1192, 409, 519, 430, 759, 819, 534, 592, 845, 1219, 34, 773, 270, 1132, 766, 797, 16, 1017, 242, 1113, 66, 1080, 1196, 972, 838, 1031, 803, 213, 100, 1262, 878, 91, 609, 500, 812, 966, 1187, 604, 413, 892, 1089, 7, 461, 298, 512, 340, 25, 928, 361, 867, 626, 750, 782, 312, 523, 60, 138, 1150, 543, 738, 704, 908, 115, 1063, 418, 283, 728, 152, 1167, 948, 434, 918, 1044, 570, 562, 1011, 956, 1257, 903, 426, 1109, 962, 746, 148, 144, 531, 763, 1193, 875, 410, 22, 520, 112, 431, 900, 760, 897, 820, 189, 535, 1270, 593, 823, 846, 52, 1220, 1121, 35, 229, 774, 192, 271, 1227, 1133, 859, 767, 1005, 798, 538, 17, 681, 1018, 686, 243, 290, 1114, 1273, 67, 1094, 1081, 347, 1197, 669, 973, 596, 839, 1038, 1032, 994, 804, 984, 214, 826, 101, 83, 1263, 167, 879, 1156, 92, 849, 610, 485, 501, 1023, 813, 942, 967, 55, 1188, 12, 605, 357, 414, 1105, 893, 1223, 1090, 79, 8, 718, 462, 651, 299, 1124, 513, 722, 341, 395, 26, 451, 929, 38, 362, 584, 868, 691, 627, 254, 751, 232, 783, 466, 313, 401, 524, 1057, 61, 777, 139, 1000, 1151, 446, 544, 1248, 739, 195, 705, 655, 909, 202, 116, 549, 1064, 274, 419, 698, 284, 248, 729, 328, 153, 1230, 1168, 303, 949, 1241, 435, 174, 919, 1136, 1045, 384, 571, 1280, 563, 1144, 1012, 862, 957, 1128, 1258, 336, 904, 1253, 427, 770, 1110, 210, 963, 295, 747, 735, 149, 1008, 145, 517, 532, 32, 764, 240, 1194, 801, 876, 810, 411, 459, 23, 624, 521, 541, 113, 726, 432, 560, 901, 744, 761, 20, 898, 187, 821, 1119, 190, 857, 536, 684, 1271, 345, 594, 992, 824, 165, 847, 1021, 53, 355, 1221, 716, 1122, 393, 36, 689, 230, 399, 775, 444, 193, 200, 272, 246, 1228, 1239, 1134, 1278, 860, 334, 768, 293, 1006, 30, 799, 457, 539, 558, 18, 1117, 682, 990, 1019, 714, 687, 442, 244, 1276, 291, 455, 1115, 712, 1274, 710, 68, 70, 1095, 634, 1082, 72, 348, 475, 1198, 1097, 670, 933, 974, 636, 597, 886, 840, 1084, 1039, 47, 1033, 74, 995, 379, 805, 350, 985, 42, 215, 477, 827, 660, 102, 1200, 84, 1181, 1264, 1099, 168, 159, 880, 672, 1157, 366, 93, 935, 850, 128, 611, 976, 486, 220, 502, 638, 1024, 494, 814, 599, 943, 588, 968, 888, 56, 914, 1189, 842, 13, 835, 606, 1086, 358, 135, 415, 1041, 1106, 872, 894, 49, 1224, 678, 1091, 1035, 80, 482, 9, 76, 719, 581, 463, 997, 652, 695, 300, 381, 1125, 207, 514, 807, 723, 184, 342, 352, 396, 1236, 27, 987, 452, 631, 930, 44, 39, 1178, 363, 217, 585, 832, 869, 479, 692, 181, 628, 829, 255, 258, 752, 662, 233, 121, 784, 104, 467, 261, 314, 1202, 402, 1074, 525, 86, 1058, 755, 62, 1183, 778, 1163, 140, 1266, 1001, 665, 1152, 1101, 447, 1053, 545, 170, 1249, 236, 740, 161, 196, 554, 706, 882, 656, 124, 910, 674, 203, 1174, 117, 1159, 550, 787, 1065, 368, 275, 791, 420, 95, 699, 107, 285, 937, 249, 323, 730, 852, 329, 470, 154, 130, 1231, 1069, 1169, 613, 304, 264, 950, 978, 1242, 618, 436, 488, 175, 317, 920, 222, 1137, 372, 1046, 504, 385, 1205, 572, 640, 1281, 1213, 564, 1026, 1145, 405, 1013, 496, 863, 279, 958, 816, 1129, 1077, 1259, 601, 337, 309, 905, 945, 1254, 528, 428, 590, 771, 795, 1111, 970, 211, 89, 964, 890, 296, 926, 748, 58, 736, 1061, 150, 916, 1009, 424, 146, 1191, 518, 758, 533, 844, 33, 269, 765, 15, 241, 65, 1195, 837, 802, 99, 877, 608, 811, 1186, 412, 1088, 460, 511, 24, 360, 625, 781, 522, 137, 542, 703, 114, 417, 727, 1166, 433, 1043, 561, 955, 902, 1108, 745, 143, 762, 874, 21, 111, 899, 896, 188, 1269, 822, 51, 1120, 228, 191, 1226, 858, 1004, 537, 680, 685, 289, 1272, 1093, 346, 668, 595, 1037, 993, 983, 825, 82, 166, 1155, 848, 484, 1022, 941, 54, 11, 356, 1104, 1222, 78, 717, 650, 1123, 721, 394, 450, 37, 583, 690, 253, 231, 465, 400, 1056, 776, 999, 445, 1247, 194, 654, 201, 548, 273, 697, 247, 327, 1229, 302, 1240, 173, 1135, 383, 1279, 1143, 861, 1127, 335, 1252, 769, 209, 294, 734, 1007, 516, 31, 239, 800, 809, 458, 623, 540, 725, 559, 743, 19, 186, 1118, 856, 683, 344, 991, 164, 1020, 354, 715, 392, 688, 398, 443, 199, 245, 1238, 1277, 333, 292, 29, 456, 557, 1116, 989, 713, 441, 1275, 454, 711, 709, 69, 633, 71, 474, 1096, 932, 635, 885, 1083, 46, 73, 378, 349, 41, 476, 659, 1199, 1180, 1098, 158, 671, 365, 934, 127, 975, 219, 637, 493, 598, 587, 887, 913, 841, 834, 1085, 134, 1040, 871, 48, 677, 1034, 481, 75, 580, 996, 694, 380, 206, 806, 183, 351, 1235, 986, 630, 43, 1177, 216, 831, 478, 180, 828, 257, 661, 120, 103, 260, 1201, 1073, 85, 754, 1182, 1162, 1265, 664, 1100, 1052, 169, 235, 160, 553, 881, 123, 673, 1173, 1158, 786, 367, 790, 94, 106, 936, 322, 851, 469, 129, 1068, 612, 263, 977, 617, 487, 316, 221, 371, 503, 1204, 639, 1212, 1025, 404, 495, 278, 815, 1076, 600, 308, 944, 527, 589, 794, 969, 88, 889, 925, 57, 1060, 915, 423, 1190, 757, 843, 268, 14, 64, 836, 98, 607, 1185, 1087, 510, 359, 780, 136, 702, 416, 1165, 1042, 954, 1107, 142, 873, 110, 895, 1268, 50, 227, 1225, 1003, 679, 288, 1092, 667, 1036, 982, 81, 1154, 483, 940, 10, 1103, 77, 649, 720, 449, 582, 252, 464, 1055, 998, 1246, 653, 547, 696, 326, 301, 172, 382, 1142, 1126, 1251, 208, 733, 515, 238, 808, 622, 724, 742, 185, 855, 343, 163, 353, 391, 397, 198, 1237, 332, 28, 556, 988, 440, 453, 708, 632, 473, 931, 884, 45, 377, 40, 658, 1179, 157, 364, 126, 218, 492, 586, 912, 833, 133, 870, 676, 480, 579, 693, 205, 182, 1234, 629, 1176, 830, 179, 256, 119, 259, 1072, 753, 1161, 663, 1051, 234, 552, 122, 1172, 785, 789, 105, 321, 468, 1067, 262, 616, 315, 370, 1203, 1211, 403, 277, 1075, 307, 526, 793, 87, 924, 1059, 422, 756, 267, 63, 97, 1184, 509, 779, 701, 1164, 953, 141, 109, 1267, 226, 1002, 287, 666, 981, 1153, 939, 1102, 648, 448, 251, 1054, 1245, 546, 325, 171, 1141, 1250, 732, 237, 621, 741, 854, 162, 390, 197, 331, 555, 439, 707, 472, 883, 376, 657, 156, 125, 491, 911, 132, 675, 578, 204, 1233, 1175, 178, 118, 1071, 1160, 1050, 551, 1171, 788, 320, 1066, 615, 369, 1210, 276, 306, 792, 923, 421, 266, 96, 508, 700, 952, 108, 225, 286, 980, 938, 647, 250, 1244, 324, 1140, 731, 620, 853, 389, 330, 438, 471, 375, 155, 490, 131, 577, 1232, 177, 1070, 1049, 1170, 319, 614, 1209, 305, 922, 265, 507, 951, 224, 979, 646, 1243, 1139, 619, 388, 437, 374, 489, 576, 176, 1048, 318, 1208, 921, 506, 223, 645, 1138, 387, 373, 575, 1047, 1207, 505, 644, 386, 574, 1206, 643, 573, 642, 641]), array('H', [0, 0, 1, 296, 2, 227, 297, 864, 3, 592, 228, 535, 298, 1061, 865, 523, 4, 1214, 593, 1266, 229, 1160, 536, 1052, 299, 454, 1062, 888, 866, 1141, 524, 1025, 5, 831, 1215, 1091, 594, 1166, 1267, 51, 230, 222, 1161, 37, 537, 819, 1053, 1032, 300, 422, 455, 204, 1063, 139, 889, 762, 867, 256, 1142, 709, 525, 555, 1026, 150, 6, 1288, 832, 602, 1216, 42, 1092, 1201, 595, 271, 1167, 750, 1268, 93, 52, 686, 231, 1184, 223, 1156, 1162, 135, 38, 131, 538, 343, 820, 619, 1054, 15, 1033, 187, 301, 645, 423, 1127, 456, 542, 205, 250, 1064, 81, 140, 101, 890, 1008, 763, 156, 868, 124, 257, 1279, 1143, 347, 710, 772, 526, 1070, 556, 518, 1027, 681, 151, 285, 7, 333, 1289, 68, 833, 824, 603, 1115, 1217, 1228, 43, 928, 1093, 22, 1202, 290, 596, 62, 272, 718, 1168, 623, 751, 471, 1269, 500, 94, 1252, 53, 854, 687, 435, 232, 610, 1185, 946, 224, 1058, 1157, 1138, 1163, 816, 136, 552, 39, 90, 132, 12, 539, 1005, 344, 678, 821, 19, 620, 851, 1055, 87, 16, 443, 1034, 446, 188, 966, 302, 979, 646, 278, 424, 1037, 1128, 480, 457, 898, 543, 699, 206, 449, 251, 338, 1065, 495, 82, 578, 141, 191, 102, 264, 891, 583, 1009, 567, 764, 969, 157, 728, 869, 1046, 125, 465, 258, 305, 1280, 389, 1144, 322, 348, 1259, 711, 982, 773, 1294, 527, 631, 1071, 174, 557, 649, 519, 1021, 1028, 146, 682, 183, 152, 281, 286, 431, 8, 962, 334, 724, 1290, 427, 69, 1082, 834, 366, 825, 639, 604, 1040, 1116, 73, 1218, 915, 1229, 989, 44, 1131, 929, 311, 1094, 196, 23, 663, 1203, 483, 291, 1086, 597, 1122, 63, 941, 273, 460, 719, 936, 1169, 117, 624, 807, 752, 901, 472, 838, 1270, 782, 501, 31, 95, 546, 1253, 801, 54, 107, 855, 377, 688, 702, 436, 370, 233, 397, 611, 1174, 1186, 209, 947, 1304, 225, 590, 1059, 1212, 1158, 452, 1139, 829, 1164, 220, 817, 420, 137, 254, 553, 1286, 40, 269, 91, 1182, 133, 341, 13, 643, 540, 79, 1006, 122, 345, 1068, 679, 331, 822, 1226, 20, 60, 621, 498, 852, 608, 1056, 814, 88, 1003, 17, 85, 444, 977, 1035, 896, 447, 493, 189, 581, 967, 1044, 303, 320, 980, 629, 647, 144, 279, 960, 425, 364, 1038, 913, 1129, 194, 481, 1120, 458, 115, 899, 780, 544, 105, 700, 395, 207, 588, 450, 218, 252, 267, 339, 77, 1066, 1224, 496, 812, 83, 894, 579, 318, 142, 362, 192, 113, 103, 586, 265, 1222, 892, 360, 584, 358, 1010, 1012, 568, 1238, 765, 1014, 970, 240, 158, 570, 729, 919, 870, 1240, 1047, 757, 126, 767, 466, 846, 259, 1016, 306, 796, 1281, 972, 390, 1233, 1145, 242, 323, 737, 349, 160, 1260, 1150, 712, 572, 983, 414, 774, 731, 1295, 993, 528, 921, 632, 906, 1072, 872, 175, 1104, 558, 1242, 650, 861, 520, 1049, 1022, 48, 1029, 759, 147, 1198, 683, 128, 184, 247, 153, 769, 282, 1112, 287, 468, 432, 1135, 9, 848, 963, 477, 335, 261, 725, 386, 1291, 1018, 428, 1079, 70, 308, 1083, 933, 835, 798, 367, 1301, 826, 1283, 640, 328, 605, 974, 1041, 957, 1117, 392, 74, 315, 1219, 1235, 916, 843, 1230, 1147, 990, 1101, 45, 244, 1132, 383, 930, 325, 312, 1098, 1095, 739, 197, 671, 24, 351, 664, 742, 1204, 162, 484, 404, 292, 1262, 1087, 200, 598, 1152, 1123, 1275, 64, 714, 942, 674, 274, 574, 461, 170, 720, 985, 937, 27, 1170, 416, 118, 999, 625, 776, 808, 354, 753, 733, 902, 1194, 473, 1297, 839, 667, 1271, 995, 783, 787, 502, 530, 32, 745, 96, 923, 547, 694, 1254, 634, 802, 1207, 55, 908, 108, 791, 856, 1074, 378, 165, 689, 874, 703, 512, 437, 177, 371, 487, 234, 1106, 398, 506, 612, 560, 1175, 407, 1187, 1244, 210, 879, 948, 652, 1305, 295, 226, 863, 591, 534, 1060, 522, 1213, 1265, 1159, 1051, 453, 887, 1140, 1024, 830, 1090, 1165, 50, 221, 36, 818, 1031, 421, 203, 138, 761, 255, 708, 554, 149, 1287, 601, 41, 1200, 270, 749, 92, 685, 1183, 1155, 134, 130, 342, 618, 14, 186, 644, 1126, 541, 249, 80, 100, 1007, 155, 123, 1278, 346, 771, 1069, 517, 680, 284, 332, 67, 823, 1114, 1227, 927, 21, 289, 61, 717, 622, 470, 499, 1251, 853, 434, 609, 945, 1057, 1137, 815, 551, 89, 11, 1004, 677, 18, 850, 86, 442, 445, 965, 978, 277, 1036, 479, 897, 698, 448, 337, 494, 577, 190, 263, 582, 566, 968, 727, 1045, 464, 304, 388, 321, 1258, 981, 1293, 630, 173, 648, 1020, 145, 182, 280, 430, 961, 723, 426, 1081, 365, 638, 1039, 72, 914, 988, 1130, 310, 195, 662, 482, 1085, 1121, 940, 459, 935, 116, 806, 900, 837, 781, 30, 545, 800, 106, 376, 701, 369, 396, 1173, 208, 1303, 589, 1211, 451, 828, 219, 419, 253, 1285, 268, 1181, 340, 642, 78, 121, 1067, 330, 1225, 59, 497, 607, 813, 1002, 84, 976, 895, 492, 580, 1043, 319, 628, 143, 959, 363, 912, 193, 1119, 114, 779, 104, 394, 587, 217, 266, 76, 1223, 811, 893, 317, 361, 112, 585, 1221, 359, 357, 1011, 1237, 1013, 239, 569, 918, 1239, 756, 766, 845, 1015, 795, 971, 1232, 241, 736, 159, 1149, 571, 413, 730, 992, 920, 905, 871, 1103, 1241, 860, 1048, 47, 758, 1197, 127, 246, 768, 1111, 467, 1134, 847, 476, 260, 385, 1017, 1078, 307, 932, 797, 1300, 1282, 327, 973, 956, 391, 314, 1234, 842, 1146, 1100, 243, 382, 324, 1097, 738, 670, 350, 741, 161, 403, 1261, 199, 1151, 1274, 713, 673, 573, 169, 984, 26, 415, 998, 775, 353, 732, 1193, 1296, 666, 994, 786, 529, 744, 922, 693, 633, 1206, 907, 790, 1073, 164, 873, 511, 176, 486, 1105, 505, 559, 406, 1243, 878, 651, 294, 862, 533, 521, 1264, 1050, 886, 1023, 1089, 49, 35, 1030, 202, 760, 707, 148, 600, 1199, 748, 684, 1154, 129, 617, 185, 1125, 248, 99, 154, 1277, 770, 516, 283, 66, 1113, 926, 288, 716, 469, 1250, 433, 944, 1136, 550, 10, 676, 849, 441, 964, 276, 478, 697, 336, 576, 262, 565, 726, 463, 387, 1257, 1292, 172, 1019, 181, 429, 722, 1080, 637, 71, 987, 309, 661, 1084, 939, 934, 805, 836, 29, 799, 375, 368, 1172, 1302, 1210, 827, 418, 1284, 1180, 641, 120, 329, 58, 606, 1001, 975, 491, 1042, 627, 958, 911, 1118, 778, 393, 216, 75, 810, 316, 111, 1220, 356, 1236, 238, 917, 755, 844, 794, 1231, 735, 1148, 412, 991, 904, 1102, 859, 46, 1196, 245, 1110, 1133, 475, 384, 1077, 931, 1299, 326, 955, 313, 841, 1099, 381, 1096, 669, 740, 402, 198, 1273, 672, 168, 25, 997, 352, 1192, 665, 785, 743, 692, 1205, 789, 163, 510, 485, 504, 405, 877, 293, 532, 1263, 885, 1088, 34, 201, 706, 599, 747, 1153, 616, 1124, 98, 1276, 515, 65, 925, 715, 1249, 943, 549, 675, 440, 275, 696, 575, 564, 462, 1256, 171, 180, 721, 636, 986, 660, 938, 804, 28, 374, 1171, 1209, 417, 1179, 119, 57, 1000, 490, 626, 910, 777, 215, 809, 110, 355, 237, 754, 793, 734, 411, 903, 858, 1195, 1109, 474, 1076, 1298, 954, 840, 380, 668, 401, 1272, 167, 996, 1191, 784, 691, 788, 509, 503, 876, 531, 884, 33, 705, 746, 615, 97, 514, 924, 1248, 548, 439, 695, 563, 1255, 179, 635, 659, 803, 373, 1208, 1178, 56, 489, 909, 214, 109, 236, 792, 410, 857, 1108, 1075, 953, 379, 400, 166, 1190, 690, 508, 875, 883, 704, 614, 513, 1247, 438, 562, 178, 658, 372, 1177, 488, 213, 235, 409, 1107, 952, 399, 1189, 507, 882, 613, 1246, 561, 657, 1176, 212, 408, 951, 1188, 881, 1245, 656, 211, 950, 880, 655, 949, 654, 653]), array('H', [0, 0, 1, 1184, 2, 1227, 1185, 382, 3, 942, 1228, 634, 1186, 748, 383, 985, 4, 1284, 943, 1354, 1229, 140, 635, 737, 1187, 1028, 749, 700, 384, 1134, 986, 1401, 5, 392, 1285, 183, 944, 924, 1355, 506, 1230, 1246, 141, 324, 636, 743, 738, 1011, 1188, 764, 1029, 1042, 750, 728, 701, 435, 385, 1112, 1135, 160, 987, 1163, 1402, 1324, 6, 549, 393, 376, 1286, 495, 184, 1292, 945, 589, 925, 786, 1356, 1016, 507, 997, 1231, 458, 1247, 859, 142, 1085, 325, 892, 637, 467, 744, 1130, 739, 1159, 1012, 1155, 1189, 825, 765, 150, 1030, 1078, 1043, 602, 751, 1367, 729, 909, 702, 1193, 436, 682, 386, 819, 1113, 538, 1136, 264, 161, 240, 988, 1268, 1164, 1004, 1403, 829, 1325, 1065, 7, 82, 550, 1175, 394, 310, 377, 501, 1287, 597, 496, 409, 185, 769, 1293, 1382, 946, 935, 590, 522, 926, 96, 787, 1057, 1357, 800, 1017, 1202, 508, 154, 998, 486, 1232, 1119, 459, 288, 1248, 193, 860, 414, 143, 70, 1086, 870, 326, 1034, 893, 1410, 638, 1344, 468, 1224, 745, 137, 1131, 921, 740, 725, 1160, 492, 1013, 1082, 1156, 1075, 1190, 261, 826, 307, 766, 93, 151, 190, 1031, 134, 1079, 90, 1044, 1047, 603, 253, 752, 562, 1368, 647, 730, 1050, 910, 125, 703, 357, 1194, 347, 437, 606, 683, 1421, 387, 544, 820, 77, 1114, 256, 539, 774, 1137, 662, 265, 812, 162, 755, 241, 623, 989, 169, 1269, 216, 1165, 565, 1005, 676, 1404, 617, 830, 1238, 1326, 1371, 1066, 843, 8, 779, 83, 1306, 551, 650, 1176, 1298, 395, 529, 311, 225, 378, 733, 502, 431, 1288, 888, 598, 236, 497, 1053, 410, 917, 186, 121, 770, 672, 1294, 913, 1383, 202, 947, 1142, 936, 583, 591, 128, 523, 1387, 927, 1334, 97, 59, 788, 706, 1058, 836, 1358, 964, 801, 901, 1018, 360, 1203, 206, 509, 695, 155, 1125, 999, 1197, 487, 342, 1233, 667, 1120, 1212, 460, 350, 289, 951, 1249, 1393, 194, 1313, 861, 440, 415, 177, 144, 282, 71, 577, 1087, 609, 871, 1146, 327, 296, 1035, 1217, 894, 686, 1411, 22, 639, 270, 1345, 1093, 469, 1424, 1225, 940, 746, 1282, 138, 1026, 1132, 390, 922, 1244, 741, 762, 726, 1110, 1161, 547, 493, 587, 1014, 456, 1083, 465, 1157, 823, 1076, 1365, 1191, 817, 262, 1266, 827, 80, 308, 595, 767, 933, 94, 798, 152, 1117, 191, 68, 1032, 1342, 135, 723, 1080, 259, 91, 132, 1045, 560, 1048, 355, 604, 542, 254, 660, 753, 167, 563, 615, 1369, 777, 648, 527, 731, 886, 1051, 119, 911, 1140, 126, 1332, 704, 962, 358, 693, 1195, 665, 348, 1391, 438, 280, 607, 294, 684, 268, 1422, 1280, 388, 760, 545, 454, 821, 815, 78, 931, 1115, 1340, 257, 558, 540, 165, 775, 884, 1138, 960, 663, 278, 266, 758, 813, 1338, 163, 958, 756, 956, 242, 244, 624, 44, 990, 246, 170, 877, 1270, 626, 217, 101, 1166, 46, 566, 980, 1006, 992, 677, 1377, 1405, 248, 618, 426, 831, 172, 1239, 63, 1327, 879, 1372, 1254, 1067, 1272, 844, 971, 9, 628, 780, 403, 84, 219, 1307, 792, 552, 103, 651, 109, 1177, 1168, 1299, 1259, 396, 48, 530, 1102, 312, 568, 226, 710, 379, 982, 734, 1398, 503, 1008, 432, 1321, 1289, 994, 889, 1152, 599, 679, 237, 1062, 498, 1379, 1054, 483, 411, 1407, 918, 1072, 187, 250, 122, 1418, 771, 620, 673, 840, 1295, 428, 914, 199, 1384, 833, 203, 339, 948, 174, 1143, 19, 937, 1241, 584, 1362, 592, 65, 129, 657, 524, 1329, 1388, 1277, 928, 881, 1335, 41, 98, 1374, 60, 968, 789, 1256, 707, 1318, 1059, 1069, 837, 336, 1359, 1274, 965, 333, 802, 846, 902, 805, 1019, 973, 361, 368, 1204, 11, 207, 849, 510, 630, 696, 320, 156, 782, 1126, 905, 1000, 405, 1198, 866, 488, 86, 343, 808, 1234, 221, 668, 55, 1121, 1309, 1213, 1022, 461, 794, 351, 115, 290, 554, 952, 976, 1250, 105, 1394, 479, 195, 653, 1314, 364, 862, 111, 441, 445, 416, 1179, 178, 371, 145, 1170, 283, 302, 72, 1301, 578, 1207, 1088, 1261, 610, 449, 872, 398, 1147, 14, 328, 50, 297, 29, 1036, 532, 1218, 210, 895, 1104, 687, 420, 1412, 314, 23, 852, 640, 570, 271, 34, 1346, 228, 1094, 513, 470, 712, 1425, 1183, 1226, 381, 941, 633, 747, 984, 1283, 1353, 139, 736, 1027, 699, 1133, 1400, 391, 182, 923, 505, 1245, 323, 742, 1010, 763, 1041, 727, 434, 1111, 159, 1162, 1323, 548, 375, 494, 1291, 588, 785, 1015, 996, 457, 858, 1084, 891, 466, 1129, 1158, 1154, 824, 149, 1077, 601, 1366, 908, 1192, 681, 818, 537, 263, 239, 1267, 1003, 828, 1064, 81, 1174, 309, 500, 596, 408, 768, 1381, 934, 521, 95, 1056, 799, 1201, 153, 485, 1118, 287, 192, 413, 69, 869, 1033, 1409, 1343, 1223, 136, 920, 724, 491, 1081, 1074, 260, 306, 92, 189, 133, 89, 1046, 252, 561, 646, 1049, 124, 356, 346, 605, 1420, 543, 76, 255, 773, 661, 811, 754, 622, 168, 215, 564, 675, 616, 1237, 1370, 842, 778, 1305, 649, 1297, 528, 224, 732, 430, 887, 235, 1052, 916, 120, 671, 912, 201, 1141, 582, 127, 1386, 1333, 58, 705, 835, 963, 900, 359, 205, 694, 1124, 1196, 341, 666, 1211, 349, 950, 1392, 1312, 439, 176, 281, 576, 608, 1145, 295, 1216, 685, 21, 269, 1092, 1423, 939, 1281, 1025, 389, 1243, 761, 1109, 546, 586, 455, 464, 822, 1364, 816, 1265, 79, 594, 932, 797, 1116, 67, 1341, 722, 258, 131, 559, 354, 541, 659, 166, 614, 776, 526, 885, 118, 1139, 1331, 961, 692, 664, 1390, 279, 293, 267, 1279, 759, 453, 814, 930, 1339, 557, 164, 883, 959, 277, 757, 1337, 957, 955, 243, 43, 245, 876, 625, 100, 45, 979, 991, 1376, 247, 425, 171, 62, 878, 1253, 1271, 970, 627, 402, 218, 791, 102, 108, 1167, 1258, 47, 1101, 567, 709, 981, 1397, 1007, 1320, 993, 1151, 678, 1061, 1378, 482, 1406, 1071, 249, 1417, 619, 839, 427, 198, 832, 338, 173, 18, 1240, 1361, 64, 656, 1328, 1276, 880, 40, 1373, 967, 1255, 1317, 1068, 335, 1273, 332, 845, 804, 972, 367, 10, 848, 629, 319, 781, 904, 404, 865, 85, 807, 220, 54, 1308, 1021, 793, 114, 553, 975, 104, 478, 652, 363, 110, 444, 1178, 370, 1169, 301, 1300, 1206, 1260, 448, 397, 13, 49, 28, 531, 209, 1103, 419, 313, 851, 569, 33, 227, 512, 711, 1182, 380, 632, 983, 1352, 735, 698, 1399, 181, 504, 322, 1009, 1040, 433, 158, 1322, 374, 1290, 784, 995, 857, 890, 1128, 1153, 148, 600, 907, 680, 536, 238, 1002, 1063, 1173, 499, 407, 1380, 520, 1055, 1200, 484, 286, 412, 868, 1408, 1222, 919, 490, 1073, 305, 188, 88, 251, 645, 123, 345, 1419, 75, 772, 810, 621, 214, 674, 1236, 841, 1304, 1296, 223, 429, 234, 915, 670, 200, 581, 1385, 57, 834, 899, 204, 1123, 340, 1210, 949, 1311, 175, 575, 1144, 1215, 20, 1091, 938, 1024, 1242, 1108, 585, 463, 1363, 1264, 593, 796, 66, 721, 130, 353, 658, 613, 525, 117, 1330, 691, 1389, 292, 1278, 452, 929, 556, 882, 276, 1336, 954, 42, 875, 99, 978, 1375, 424, 61, 1252, 969, 401, 790, 107, 1257, 1100, 708, 1396, 1319, 1150, 1060, 481, 1070, 1416, 838, 197, 337, 17, 1360, 655, 1275, 39, 966, 1316, 334, 331, 803, 366, 847, 318, 903, 864, 806, 53, 1020, 113, 974, 477, 362, 443, 369, 300, 1205, 447, 12, 27, 208, 418, 850, 32, 511, 1181, 631, 1351, 697, 180, 321, 1039, 157, 373, 783, 856, 1127, 147, 906, 535, 1001, 1172, 406, 519, 1199, 285, 867, 1221, 489, 304, 87, 644, 344, 74, 809, 213, 1235, 1303, 222, 233, 669, 580, 56, 898, 1122, 1209, 1310, 574, 1214, 1090, 1023, 1107, 462, 1263, 795, 720, 352, 612, 116, 690, 291, 451, 555, 275, 953, 874, 977, 423, 1251, 400, 106, 1099, 1395, 1149, 480, 1415, 196, 16, 654, 38, 1315, 330, 365, 317, 863, 52, 112, 476, 442, 299, 446, 26, 417, 31, 1180, 1350, 179, 1038, 372, 855, 146, 534, 1171, 518, 284, 1220, 303, 643, 73, 212, 1302, 232, 579, 897, 1208, 573, 1089, 1106, 1262, 719, 611, 689, 450, 274, 873, 422, 399, 1098, 1148, 1414, 15, 37, 329, 316, 51, 475, 298, 25, 30, 1349, 1037, 854, 533, 517, 1219, 642, 211, 231, 896, 572, 1105, 718, 688, 273, 421, 1097, 1413, 36, 315, 474, 24, 1348, 853, 516, 641, 230, 571, 717, 272, 1096, 35, 473, 1347, 515, 229, 716, 1095, 472, 514, 715, 471, 714, 713]), array('H', [0, 0, 1, 186, 2, 161, 187, 1025, 3, 372, 162, 825, 188, 195, 1026, 347, 4, 491, 373, 782, 163, 1211, 826, 1432, 189, 322, 196, 558, 1027, 911, 348, 235, 5, 1011, 492, 1186, 374, 545, 783, 381, 164, 403, 1212, 1470, 827, 533, 1433, 16, 190, 528, 323, 677, 197, 115, 559, 986, 1028, 968, 912, 629, 349, 1201, 236, 1397, 6, 356, 1012, 463, 493, 96, 1187, 1077, 375, 473, 546, 508, 784, 328, 382, 805, 165, 744, 404, 1299, 1213, 652, 1471, 1097, 828, 432, 534, 1220, 1434, 421, 17, 943, 191, 907, 529, 1197, 324, 417, 678, 479, 198, 1372, 116, 57, 560, 682, 987, 731, 1029, 1125, 969, 71, 913, 567, 630, 1516, 350, 128, 1202, 589, 237, 483, 1398, 1334, 7, 134, 357, 340, 1013, 285, 464, 719, 494, 1462, 97, 884, 1188, 202, 1078, 1020, 376, 1072, 474, 714, 547, 88, 509, 794, 785, 863, 329, 396, 383, 1376, 806, 301, 166, 935, 745, 1417, 405, 1172, 1300, 552, 1214, 390, 653, 1154, 1472, 120, 1098, 1347, 829, 815, 433, 456, 535, 1266, 1221, 1387, 1435, 706, 422, 1316, 18, 61, 944, 158, 192, 1208, 908, 542, 530, 112, 1198, 93, 325, 649, 418, 414, 679, 564, 480, 282, 199, 85, 1373, 1169, 117, 1263, 58, 109, 561, 1260, 683, 659, 988, 686, 732, 1280, 1030, 694, 1126, 1509, 970, 662, 72, 514, 914, 1057, 568, 177, 631, 991, 1517, 1006, 351, 902, 129, 930, 1203, 689, 590, 977, 238, 1485, 484, 1065, 1399, 735, 1335, 838, 8, 595, 135, 48, 358, 1283, 341, 799, 1014, 276, 286, 618, 465, 1033, 720, 292, 495, 1406, 1463, 1147, 98, 697, 885, 607, 1189, 1230, 203, 1160, 1079, 1129, 1021, 1428, 377, 982, 1073, 1093, 475, 1512, 715, 790, 548, 1383, 89, 105, 510, 973, 795, 603, 786, 1362, 864, 27, 330, 665, 397, 1366, 384, 1051, 1377, 36, 807, 75, 302, 214, 167, 243, 936, 1273, 746, 517, 1418, 868, 406, 1041, 1173, 852, 1301, 917, 553, 624, 1215, 584, 391, 1311, 654, 1060, 1155, 31, 1473, 257, 121, 1478, 1099, 571, 1348, 753, 830, 1490, 816, 1238, 434, 180, 457, 334, 536, 42, 1267, 314, 1222, 634, 1388, 223, 1436, 775, 707, 1140, 423, 994, 1317, 669, 19, 1106, 62, 262, 945, 1520, 159, 370, 193, 489, 1209, 320, 909, 1009, 543, 401, 531, 526, 113, 966, 1199, 354, 94, 471, 326, 742, 650, 430, 419, 905, 415, 1370, 680, 1123, 565, 126, 481, 132, 283, 1460, 200, 1070, 86, 861, 1374, 933, 1170, 388, 118, 813, 1264, 704, 59, 1206, 110, 647, 562, 83, 1261, 1258, 684, 692, 660, 1055, 989, 900, 687, 1483, 733, 593, 1281, 274, 1031, 1404, 695, 1228, 1127, 980, 1510, 1381, 971, 1360, 663, 1049, 73, 241, 515, 1039, 915, 582, 1058, 255, 569, 1488, 178, 40, 632, 773, 992, 1104, 1518, 487, 1007, 524, 352, 740, 903, 1121, 130, 1068, 931, 811, 1204, 81, 690, 898, 591, 1402, 978, 1358, 239, 580, 1486, 771, 485, 738, 1066, 79, 1400, 578, 736, 576, 1336, 1338, 839, 1498, 9, 1340, 596, 640, 136, 841, 49, 306, 359, 1500, 1284, 1247, 342, 11, 800, 726, 1015, 1342, 277, 1001, 287, 598, 619, 218, 466, 642, 1034, 1353, 721, 138, 293, 1452, 496, 843, 1407, 444, 1464, 51, 1148, 171, 99, 308, 698, 892, 886, 361, 608, 143, 1190, 1502, 1231, 1114, 204, 1286, 1161, 247, 1080, 1249, 1130, 758, 1022, 344, 1429, 232, 378, 13, 983, 1394, 1074, 802, 1094, 940, 476, 728, 1513, 1331, 716, 1017, 791, 298, 549, 1344, 1384, 155, 90, 279, 106, 1277, 511, 1003, 974, 835, 796, 289, 604, 1425, 787, 600, 1363, 211, 865, 621, 28, 750, 331, 220, 666, 367, 398, 468, 1367, 1457, 385, 644, 1052, 271, 1378, 1036, 37, 521, 808, 1355, 76, 1495, 303, 723, 215, 1449, 168, 140, 244, 229, 937, 295, 1274, 1422, 747, 1454, 518, 1446, 1419, 498, 869, 501, 407, 845, 1042, 1324, 1174, 1409, 853, 872, 1302, 446, 918, 821, 554, 1466, 625, 504, 1216, 53, 585, 880, 392, 1150, 1312, 410, 655, 173, 1061, 614, 1156, 101, 32, 848, 1474, 310, 258, 962, 122, 700, 1479, 1045, 1100, 894, 572, 1243, 1349, 888, 754, 1327, 831, 363, 1491, 1442, 817, 610, 1239, 1177, 435, 145, 181, 1181, 458, 1192, 335, 1412, 537, 1504, 43, 1088, 1268, 1233, 315, 856, 1223, 1116, 635, 439, 1389, 206, 224, 875, 1437, 1288, 776, 1293, 708, 1163, 1141, 1305, 424, 249, 995, 149, 1318, 1082, 670, 449, 20, 1251, 1107, 955, 63, 1132, 263, 921, 946, 760, 1521, 185, 160, 1024, 371, 824, 194, 346, 490, 781, 1210, 1431, 321, 557, 910, 234, 1010, 1185, 544, 380, 402, 1469, 532, 15, 527, 676, 114, 985, 967, 628, 1200, 1396, 355, 462, 95, 1076, 472, 507, 327, 804, 743, 1298, 651, 1096, 431, 1219, 420, 942, 906, 1196, 416, 478, 1371, 56, 681, 730, 1124, 70, 566, 1515, 127, 588, 482, 1333, 133, 339, 284, 718, 1461, 883, 201, 1019, 1071, 713, 87, 793, 862, 395, 1375, 300, 934, 1416, 1171, 551, 389, 1153, 119, 1346, 814, 455, 1265, 1386, 705, 1315, 60, 157, 1207, 541, 111, 92, 648, 413, 563, 281, 84, 1168, 1262, 108, 1259, 658, 685, 1279, 693, 1508, 661, 513, 1056, 176, 990, 1005, 901, 929, 688, 976, 1484, 1064, 734, 837, 594, 47, 1282, 798, 275, 617, 1032, 291, 1405, 1146, 696, 606, 1229, 1159, 1128, 1427, 981, 1092, 1511, 789, 1382, 104, 972, 602, 1361, 26, 664, 1365, 1050, 35, 74, 213, 242, 1272, 516, 867, 1040, 851, 916, 623, 583, 1310, 1059, 30, 256, 1477, 570, 752, 1489, 1237, 179, 333, 41, 313, 633, 222, 774, 1139, 993, 668, 1105, 261, 1519, 369, 488, 319, 1008, 400, 525, 965, 353, 470, 741, 429, 904, 1369, 1122, 125, 131, 1459, 1069, 860, 932, 387, 812, 703, 1205, 646, 82, 1257, 691, 1054, 899, 1482, 592, 273, 1403, 1227, 979, 1380, 1359, 1048, 240, 1038, 581, 254, 1487, 39, 772, 1103, 486, 523, 739, 1120, 1067, 810, 80, 897, 1401, 1357, 579, 770, 737, 78, 577, 575, 1337, 1497, 1339, 639, 840, 305, 1499, 1246, 10, 725, 1341, 1000, 597, 217, 641, 1352, 137, 1451, 842, 443, 50, 170, 307, 891, 360, 142, 1501, 1113, 1285, 246, 1248, 757, 343, 231, 12, 1393, 801, 939, 727, 1330, 1016, 297, 1343, 154, 278, 1276, 1002, 834, 288, 1424, 599, 210, 620, 749, 219, 366, 467, 1456, 643, 270, 1035, 520, 1354, 1494, 722, 1448, 139, 228, 294, 1421, 1453, 1445, 497, 500, 844, 1323, 1408, 871, 445, 820, 1465, 503, 52, 879, 1149, 409, 172, 613, 100, 847, 309, 961, 699, 1044, 893, 1242, 887, 1326, 362, 1441, 609, 1176, 144, 1180, 1191, 1411, 1503, 1087, 1232, 855, 1115, 438, 205, 874, 1287, 1292, 1162, 1304, 248, 148, 1081, 448, 1250, 954, 1131, 920, 759, 184, 1023, 823, 345, 780, 1430, 556, 233, 1184, 379, 1468, 14, 675, 984, 627, 1395, 461, 1075, 506, 803, 1297, 1095, 1218, 941, 1195, 477, 55, 729, 69, 1514, 587, 1332, 338, 717, 882, 1018, 712, 792, 394, 299, 1415, 550, 1152, 1345, 454, 1385, 1314, 156, 540, 91, 412, 280, 1167, 107, 657, 1278, 1507, 512, 175, 1004, 928, 975, 1063, 836, 46, 797, 616, 290, 1145, 605, 1158, 1426, 1091, 788, 103, 601, 25, 1364, 34, 212, 1271, 866, 850, 622, 1309, 29, 1476, 751, 1236, 332, 312, 221, 1138, 667, 260, 368, 318, 399, 964, 469, 428, 1368, 124, 1458, 859, 386, 702, 645, 1256, 1053, 1481, 272, 1226, 1379, 1047, 1037, 253, 38, 1102, 522, 1119, 809, 896, 1356, 769, 77, 574, 1496, 638, 304, 1245, 724, 999, 216, 1351, 1450, 442, 169, 890, 141, 1112, 245, 756, 230, 1392, 938, 1329, 296, 153, 1275, 833, 1423, 209, 748, 365, 1455, 269, 519, 1493, 1447, 227, 1420, 1444, 499, 1322, 870, 819, 502, 878, 408, 612, 846, 960, 1043, 1241, 1325, 1440, 1175, 1179, 1410, 1086, 854, 437, 873, 1291, 1303, 147, 447, 953, 919, 183, 822, 779, 555, 1183, 1467, 674, 626, 460, 505, 1296, 1217, 1194, 54, 68, 586, 337, 881, 711, 393, 1414, 1151, 453, 1313, 539, 411, 1166, 656, 1506, 174, 927, 1062, 45, 615, 1144, 1157, 1090, 102, 24, 33, 1270, 849, 1308, 1475, 1235, 311, 1137, 259, 317, 963, 427, 123, 858, 701, 1255, 1480, 1225, 1046, 252, 1101, 1118, 895, 768, 573, 637, 1244, 998, 1350, 441, 889, 1111, 755, 1391, 1328, 152, 832, 208, 364, 268, 1492, 226, 1443, 1321, 818, 877, 611, 959, 1240, 1439, 1178, 1085, 436, 1290, 146, 952, 182, 778, 1182, 673, 459, 1295, 1193, 67, 336, 710, 1413, 452, 538, 1165, 1505, 926, 44, 1143, 1089, 23, 1269, 1307, 1234, 1136, 316, 426, 857, 1254, 1224, 251, 1117, 767, 636, 997, 440, 1110, 1390, 151, 207, 267, 225, 1320, 876, 958, 1438, 1084, 1289, 951, 777, 672, 1294, 66, 709, 451, 1164, 925, 1142, 22, 1306, 1135, 425, 1253, 250, 766, 996, 1109, 150, 266, 1319, 957, 1083, 950, 671, 65, 450, 924, 21, 1134, 1252, 765, 1108, 265, 956, 949, 64, 923, 1133, 764, 264, 948, 922, 763, 947, 762, 761]), array('H', [0, 0, 1, 754, 2, 218, 755, 1259, 3, 1508, 219, 774, 756, 101, 1260, 972, 4, 960, 1509, 1251, 220, 395, 775, 839, 757, 436, 102, 644, 1261, 574, 973, 347, 5, 1528, 961, 1477, 1510, 732, 1252, 855, 221, 174, 396, 1338, 776, 108, 840, 243, 758, 900, 437, 96, 103, 410, 645, 992, 1262, 387, 575, 267, 974, 617, 348, 1149, 6, 319, 1529, 826, 962, 1593, 1478, 421, 1511, 135, 733, 1190, 1253, 415, 856, 1444, 222, 1398, 175, 1572, 397, 1178, 1339, 1328, 777, 260, 109, 1360, 841, 1101, 244, 1469, 759, 13, 901, 664, 438, 1559, 97, 570, 104, 613, 411, 1097, 646, 650, 993, 1486, 1263, 281, 388, 1057, 576, 1609, 268, 601, 975, 1548, 618, 928, 349, 654, 1150, 1522, 7, 474, 320, 296, 1530, 892, 827, 862, 963, 1298, 1594, 144, 1479, 997, 422, 875, 1512, 792, 136, 36, 734, 1064, 1191, 1240, 1254, 850, 416, 565, 857, 1490, 1445, 1164, 223, 480, 1399, 555, 176, 128, 1573, 1495, 398, 202, 1179, 1141, 1340, 1267, 1329, 77, 778, 1021, 261, 922, 110, 329, 1361, 1371, 842, 950, 1102, 116, 245, 285, 1470, 548, 760, 378, 14, 1073, 902, 526, 665, 1450, 439, 1580, 1560, 215, 98, 392, 571, 729, 105, 407, 614, 1590, 412, 1175, 1098, 1556, 647, 1606, 651, 889, 994, 1061, 1487, 125, 1264, 326, 282, 523, 389, 1172, 1058, 1169, 577, 1115, 1610, 461, 269, 580, 602, 1004, 976, 1321, 1549, 534, 619, 1118, 929, 1352, 350, 708, 655, 335, 1151, 1613, 1523, 314, 8, 469, 475, 373, 321, 464, 297, 228, 1531, 628, 893, 1014, 828, 272, 863, 504, 964, 496, 1299, 1210, 1595, 583, 145, 237, 1480, 71, 998, 689, 423, 605, 876, 1433, 1513, 302, 793, 767, 137, 1007, 37, 485, 735, 1418, 1065, 940, 1192, 979, 1241, 695, 1255, 835, 851, 988, 417, 1324, 566, 597, 858, 1236, 1491, 1367, 1446, 1552, 1165, 1348, 224, 233, 481, 593, 1400, 537, 556, 1404, 177, 1502, 129, 1292, 1574, 622, 1496, 1044, 399, 1311, 203, 1035, 1180, 1121, 1142, 541, 1341, 193, 1268, 358, 1330, 932, 78, 745, 779, 1536, 1022, 639, 262, 1355, 923, 560, 111, 884, 330, 684, 1362, 353, 1372, 429, 843, 64, 951, 51, 1103, 711, 117, 1408, 246, 675, 286, 1377, 1471, 658, 549, 517, 761, 633, 379, 1228, 15, 338, 1074, 181, 903, 1050, 527, 44, 666, 1154, 1451, 28, 440, 161, 1581, 448, 1561, 1616, 216, 1506, 99, 958, 393, 434, 572, 1526, 730, 172, 106, 898, 408, 385, 615, 317, 1591, 133, 413, 1396, 1176, 258, 1099, 11, 1557, 611, 648, 279, 1607, 1546, 652, 472, 890, 1296, 995, 790, 1062, 848, 1488, 478, 126, 200, 1265, 1019, 327, 948, 283, 376, 524, 1578, 390, 405, 1173, 1604, 1059, 324, 1170, 1113, 578, 1319, 1116, 706, 1611, 467, 462, 626, 270, 494, 581, 69, 603, 300, 1005, 1416, 977, 833, 1322, 1234, 1550, 231, 535, 1500, 620, 1309, 1119, 191, 930, 1534, 1353, 882, 351, 62, 709, 673, 656, 631, 336, 1048, 1152, 159, 1614, 956, 1524, 896, 315, 1394, 9, 277, 470, 788, 476, 1017, 374, 403, 322, 1317, 465, 492, 298, 831, 229, 1307, 1532, 60, 629, 157, 894, 275, 1015, 1315, 829, 58, 273, 56, 864, 866, 505, 1083, 965, 868, 497, 21, 1300, 507, 1211, 207, 1596, 1085, 584, 86, 146, 967, 238, 1439, 1481, 870, 72, 724, 999, 499, 690, 1039, 424, 23, 606, 1108, 877, 1302, 1434, 1275, 1514, 509, 303, 1132, 794, 1213, 768, 1184, 138, 209, 1008, 1286, 38, 1598, 486, 1280, 736, 1087, 1419, 819, 1066, 586, 941, 1125, 1193, 88, 980, 716, 1242, 148, 696, 806, 1256, 969, 836, 344, 852, 240, 989, 1146, 418, 1441, 1325, 1466, 567, 1483, 598, 1519, 859, 872, 1237, 1161, 1492, 74, 1368, 545, 1447, 726, 1553, 122, 1166, 1001, 1349, 311, 225, 501, 234, 1430, 482, 692, 594, 1345, 1401, 1041, 538, 742, 557, 426, 1405, 514, 178, 25, 1503, 169, 130, 608, 1293, 197, 1575, 1110, 623, 1413, 1497, 879, 1045, 1391, 400, 1304, 1312, 1080, 204, 1436, 1036, 1272, 1181, 1277, 1122, 803, 1143, 1516, 542, 308, 1342, 511, 194, 1388, 1269, 305, 359, 362, 1331, 1134, 933, 251, 79, 796, 746, 365, 780, 1215, 1537, 1200, 1023, 770, 640, 1334, 263, 1186, 1356, 1093, 924, 140, 561, 1137, 112, 211, 885, 457, 331, 1010, 685, 936, 1363, 1288, 354, 680, 1373, 40, 430, 254, 844, 1600, 65, 187, 952, 488, 52, 82, 1104, 1282, 712, 1462, 118, 738, 1409, 799, 247, 1089, 676, 1458, 287, 1421, 1378, 749, 1472, 821, 659, 291, 550, 1068, 518, 368, 762, 588, 634, 1223, 380, 943, 1229, 783, 16, 1127, 339, 1425, 1075, 1195, 182, 1218, 904, 90, 1051, 916, 528, 982, 45, 1540, 667, 718, 1155, 1382, 1452, 1244, 29, 1203, 441, 150, 162, 909, 1582, 698, 449, 1026, 1562, 808, 1617, 753, 217, 1258, 1507, 773, 100, 971, 959, 1250, 394, 838, 435, 643, 573, 346, 1527, 1476, 731, 854, 173, 1337, 107, 242, 899, 95, 409, 991, 386, 266, 616, 1148, 318, 825, 1592, 420, 134, 1189, 414, 1443, 1397, 1571, 1177, 1327, 259, 1359, 1100, 1468, 12, 663, 1558, 569, 612, 1096, 649, 1485, 280, 1056, 1608, 600, 1547, 927, 653, 1521, 473, 295, 891, 861, 1297, 143, 996, 874, 791, 35, 1063, 1239, 849, 564, 1489, 1163, 479, 554, 127, 1494, 201, 1140, 1266, 76, 1020, 921, 328, 1370, 949, 115, 284, 547, 377, 1072, 525, 1449, 1579, 214, 391, 728, 406, 1589, 1174, 1555, 1605, 888, 1060, 124, 325, 522, 1171, 1168, 1114, 460, 579, 1003, 1320, 533, 1117, 1351, 707, 334, 1612, 313, 468, 372, 463, 227, 627, 1013, 271, 503, 495, 1209, 582, 236, 70, 688, 604, 1432, 301, 766, 1006, 484, 1417, 939, 978, 694, 834, 987, 1323, 596, 1235, 1366, 1551, 1347, 232, 592, 536, 1403, 1501, 1291, 621, 1043, 1310, 1034, 1120, 540, 192, 357, 931, 744, 1535, 638, 1354, 559, 883, 683, 352, 428, 63, 50, 710, 1407, 674, 1376, 657, 516, 632, 1227, 337, 180, 1049, 43, 1153, 27, 160, 447, 1615, 1505, 957, 433, 1525, 171, 897, 384, 316, 132, 1395, 257, 10, 610, 278, 1545, 471, 1295, 789, 847, 477, 199, 1018, 947, 375, 1577, 404, 1603, 323, 1112, 1318, 705, 466, 625, 493, 68, 299, 1415, 832, 1233, 230, 1499, 1308, 190, 1533, 881, 61, 672, 630, 1047, 158, 955, 895, 1393, 276, 787, 1016, 402, 1316, 491, 830, 1306, 59, 156, 274, 1314, 57, 55, 865, 1082, 867, 20, 506, 206, 1084, 85, 966, 1438, 869, 723, 498, 1038, 22, 1107, 1301, 1274, 508, 1131, 1212, 1183, 208, 1285, 1597, 1279, 1086, 818, 585, 1124, 87, 715, 147, 805, 968, 343, 239, 1145, 1440, 1465, 1482, 1518, 871, 1160, 73, 544, 725, 121, 1000, 310, 500, 1429, 691, 1344, 1040, 741, 425, 513, 24, 168, 607, 196, 1109, 1412, 878, 1390, 1303, 1079, 1435, 1271, 1276, 802, 1515, 307, 510, 1387, 304, 361, 1133, 250, 795, 364, 1214, 1199, 769, 1333, 1185, 1092, 139, 1136, 210, 456, 1009, 935, 1287, 679, 39, 253, 1599, 186, 487, 81, 1281, 1461, 737, 798, 1088, 1457, 1420, 748, 820, 290, 1067, 367, 587, 1222, 942, 782, 1126, 1424, 1194, 1217, 89, 915, 981, 1539, 717, 1381, 1243, 1202, 149, 908, 697, 1025, 807, 752, 1257, 772, 970, 1249, 837, 642, 345, 1475, 853, 1336, 241, 94, 990, 265, 1147, 824, 419, 1188, 1442, 1570, 1326, 1358, 1467, 662, 568, 1095, 1484, 1055, 599, 926, 1520, 294, 860, 142, 873, 34, 1238, 563, 1162, 553, 1493, 1139, 75, 920, 1369, 114, 546, 1071, 1448, 213, 727, 1588, 1554, 887, 123, 521, 1167, 459, 1002, 532, 1350, 333, 312, 371, 226, 1012, 502, 1208, 235, 687, 1431, 765, 483, 938, 693, 986, 595, 1365, 1346, 591, 1402, 1290, 1042, 1033, 539, 356, 743, 637, 558, 682, 427, 49, 1406, 1375, 515, 1226, 179, 42, 26, 446, 1504, 432, 170, 383, 131, 256, 609, 1544, 1294, 846, 198, 946, 1576, 1602, 1111, 704, 624, 67, 1414, 1232, 1498, 189, 880, 671, 1046, 954, 1392, 786, 401, 490, 1305, 155, 1313, 54, 1081, 19, 205, 84, 1437, 722, 1037, 1106, 1273, 1130, 1182, 1284, 1278, 817, 1123, 714, 804, 342, 1144, 1464, 1517, 1159, 543, 120, 309, 1428, 1343, 740, 512, 167, 195, 1411, 1389, 1078, 1270, 801, 306, 1386, 360, 249, 363, 1198, 1332, 1091, 1135, 455, 934, 678, 252, 185, 80, 1460, 797, 1456, 747, 289, 366, 1221, 781, 1423, 1216, 914, 1538, 1380, 1201, 907, 1024, 751, 771, 1248, 641, 1474, 1335, 93, 264, 823, 1187, 1569, 1357, 661, 1094, 1054, 925, 293, 141, 33, 562, 552, 1138, 919, 113, 1070, 212, 1587, 886, 520, 458, 531, 332, 370, 1011, 1207, 686, 764, 937, 985, 1364, 590, 1289, 1032, 355, 636, 681, 48, 1374, 1225, 41, 445, 431, 382, 255, 1543, 845, 945, 1601, 703, 66, 1231, 188, 670, 953, 785, 489, 154, 53, 18, 83, 721, 1105, 1129, 1283, 816, 713, 341, 1463, 1158, 119, 1427, 739, 166, 1410, 1077, 800, 1385, 248, 1197, 1090, 454, 677, 184, 1459, 1455, 288, 1220, 1422, 913, 1379, 906, 750, 1247, 1473, 92, 822, 1568, 660, 1053, 292, 32, 551, 918, 1069, 1586, 519, 530, 369, 1206, 763, 984, 589, 1031, 635, 47, 1224, 444, 381, 1542, 944, 702, 1230, 669, 784, 153, 17, 720, 1128, 815, 340, 1157, 1426, 165, 1076, 1384, 1196, 453, 183, 1454, 1219, 912, 905, 1246, 91, 1567, 1052, 31, 917, 1585, 529, 1205, 983, 1030, 46, 443, 1541, 701, 668, 152, 719, 814, 1156, 164, 1383, 452, 1453, 911, 1245, 1566, 30, 1584, 1204, 1029, 442, 700, 151, 813, 163, 451, 910, 1565, 1583, 1028, 699, 812, 450, 1564, 1027, 811, 1563, 810, 809]), array('H', [0, 0, 1, 396, 2, 617, 397, 246, 3, 792, 618, 1219, 398, 1020, 247, 1013, 4, 1099, 793, 1869, 619, 642, 1220, 590, 399, 1234, 1021, 1188, 248, 536, 1014, 1459, 5, 1615, 1100, 863, 794, 77, 1870, 1416, 620, 1004, 643, 745, 1221, 1409, 591, 1521, 400, 492, 1235, 1495, 1022, 1112, 1189, 1836, 249, 359, 537, 911, 1015, 1404, 1460, 1038, 6, 1637, 1616, 258, 1101, 986, 864, 1336, 795, 724, 78, 1630, 1871, 1465, 1417, 1773, 621, 1584, 1005, 1317, 644, 1716, 746, 932, 1222, 275, 1410, 1266, 592, 1855, 1522, 580, 401, 996, 493, 105, 1236, 435, 1496, 1272, 1023, 1259, 1113, 1076, 1190, 1043, 1837, 473, 250, 1054, 360, 1207, 538, 1812, 912, 1345, 1016, 532, 1405, 1400, 1461, 1851, 1039, 1847, 7, 1141, 1638, 1430, 1617, 209, 259, 1805, 1102, 972, 987, 1169, 865, 11, 1337, 333, 796, 1153, 725, 888, 79, 1900, 1631, 1135, 1872, 1891, 1466, 170, 1418, 1145, 1774, 1508, 622, 836, 1585, 94, 1006, 326, 1318, 598, 645, 134, 1717, 755, 747, 1642, 933, 1480, 1223, 1307, 276, 241, 1411, 1331, 1267, 1800, 593, 694, 1856, 412, 1523, 1434, 581, 1684, 402, 1878, 997, 127, 494, 420, 106, 699, 1237, 654, 436, 782, 1497, 1621, 1273, 1382, 1024, 1182, 1260, 164, 1114, 1732, 1077, 1362, 1191, 1705, 1044, 1120, 1838, 213, 474, 444, 251, 120, 1055, 310, 361, 674, 1208, 1861, 539, 1695, 1813, 232, 913, 263, 1346, 614, 1017, 639, 533, 74, 1406, 1109, 1401, 983, 1462, 1713, 1852, 432, 1040, 1809, 1848, 206, 8, 1897, 1142, 323, 1639, 1328, 1431, 417, 1618, 1729, 210, 671, 260, 1106, 1806, 1325, 1103, 1662, 973, 547, 988, 1665, 1170, 345, 866, 769, 12, 1738, 1338, 976, 334, 1250, 797, 292, 1154, 1392, 726, 550, 889, 1528, 80, 501, 1901, 1610, 1632, 991, 1136, 831, 1873, 115, 1892, 287, 1467, 1668, 171, 1560, 1419, 1092, 1146, 1655, 1775, 1173, 1509, 1755, 623, 1472, 837, 1062, 1586, 348, 95, 1439, 1007, 1767, 327, 1376, 1319, 869, 599, 875, 646, 810, 135, 1450, 1718, 772, 756, 738, 748, 1603, 1643, 1083, 934, 15, 1481, 302, 1224, 1673, 1308, 47, 277, 1741, 242, 586, 1412, 1832, 1332, 928, 1268, 1341, 1801, 1131, 594, 1796, 695, 1358, 1857, 979, 413, 341, 1524, 1556, 1435, 734, 582, 337, 1685, 1292, 403, 176, 1879, 1537, 998, 1253, 128, 1689, 495, 1826, 421, 484, 107, 800, 700, 605, 1238, 1782, 655, 573, 437, 295, 783, 1296, 1498, 370, 1622, 1368, 1274, 1157, 1383, 28, 1025, 1565, 1183, 906, 1261, 1395, 165, 407, 1115, 427, 1733, 1650, 1078, 729, 1363, 845, 1192, 525, 1706, 1549, 1045, 553, 1121, 180, 1839, 1284, 214, 850, 475, 892, 445, 390, 252, 1424, 121, 317, 1056, 1531, 311, 1883, 362, 818, 675, 381, 1209, 83, 1862, 881, 540, 566, 1696, 461, 1814, 504, 233, 1541, 914, 58, 264, 1197, 1347, 1904, 615, 790, 1018, 1097, 640, 1232, 534, 1613, 75, 1002, 1407, 490, 1110, 357, 1402, 1635, 984, 722, 1463, 1582, 1714, 273, 1853, 994, 433, 1257, 1041, 1052, 1810, 530, 1849, 1139, 207, 970, 9, 1151, 1898, 1889, 1143, 834, 324, 132, 1640, 1305, 1329, 692, 1432, 1876, 418, 652, 1619, 1180, 1730, 1703, 211, 118, 672, 1693, 261, 637, 1107, 1711, 1807, 1895, 1326, 1727, 1104, 1660, 1663, 767, 974, 290, 548, 499, 989, 113, 1666, 1090, 1171, 1470, 346, 1765, 867, 808, 770, 1601, 13, 1671, 1739, 1830, 1339, 1794, 977, 1554, 335, 174, 1251, 1824, 798, 1780, 293, 368, 1155, 1563, 1393, 425, 727, 523, 551, 1282, 890, 1422, 1529, 816, 81, 564, 502, 56, 1902, 1095, 1611, 488, 1633, 1580, 992, 1050, 1137, 1149, 832, 1303, 1874, 1178, 116, 635, 1893, 1658, 288, 111, 1468, 806, 1669, 1792, 172, 1778, 1561, 521, 1420, 562, 1093, 1578, 1147, 1176, 1656, 804, 1776, 560, 1174, 558, 1510, 1512, 1756, 222, 624, 1514, 1473, 824, 838, 1758, 1063, 704, 1587, 224, 349, 195, 96, 626, 1440, 141, 1008, 1516, 1768, 468, 328, 1475, 1377, 609, 1320, 826, 870, 1126, 600, 840, 876, 717, 647, 1760, 811, 516, 136, 1065, 1451, 1242, 1719, 706, 773, 941, 757, 1589, 739, 1070, 749, 226, 1604, 922, 1644, 351, 1084, 1786, 935, 197, 16, 185, 1482, 98, 303, 40, 1225, 628, 1674, 681, 1309, 1442, 48, 659, 278, 143, 1742, 950, 243, 1010, 587, 1456, 1413, 1518, 1833, 1035, 1333, 1770, 929, 577, 1269, 470, 1342, 1844, 1802, 330, 1132, 1505, 595, 1477, 1797, 1681, 696, 1379, 1359, 441, 1858, 611, 980, 203, 414, 1322, 342, 1247, 1525, 828, 1557, 1752, 1436, 872, 735, 299, 583, 1128, 338, 1289, 1686, 602, 1293, 25, 404, 842, 177, 387, 1880, 878, 1538, 787, 999, 719, 1254, 967, 129, 649, 1690, 1724, 496, 1762, 1827, 1821, 422, 813, 485, 1300, 108, 518, 801, 219, 701, 138, 606, 714, 1239, 1067, 1783, 37, 656, 1453, 574, 1502, 438, 1244, 296, 22, 784, 1721, 1297, 711, 1499, 708, 371, 152, 1623, 775, 1369, 374, 1275, 943, 1158, 855, 1384, 759, 29, 155, 1026, 1591, 1566, 1215, 1184, 741, 907, 1626, 1262, 1072, 1396, 1165, 166, 751, 408, 778, 1116, 228, 428, 667, 1734, 1606, 1651, 1372, 1079, 924, 730, 480, 1364, 1646, 846, 377, 1193, 353, 526, 688, 1707, 1086, 1550, 1278, 1046, 1788, 554, 191, 1122, 937, 181, 946, 1840, 199, 1285, 963, 215, 18, 851, 1161, 476, 187, 893, 897, 446, 1484, 391, 858, 253, 100, 1425, 89, 122, 305, 318, 1387, 1057, 42, 1532, 901, 312, 1227, 1884, 762, 363, 630, 819, 511, 676, 1676, 382, 32, 1210, 683, 84, 450, 1863, 1311, 882, 158, 541, 1444, 567, 455, 1697, 50, 462, 1029, 1815, 661, 505, 1488, 234, 280, 1542, 1594, 915, 145, 59, 66, 265, 1744, 1198, 1569, 1348, 952, 1905, 395, 616, 245, 791, 1218, 1019, 1012, 1098, 1868, 641, 589, 1233, 1187, 535, 1458, 1614, 862, 76, 1415, 1003, 744, 1408, 1520, 491, 1494, 1111, 1835, 358, 910, 1403, 1037, 1636, 257, 985, 1335, 723, 1629, 1464, 1772, 1583, 1316, 1715, 931, 274, 1265, 1854, 579, 995, 104, 434, 1271, 1258, 1075, 1042, 472, 1053, 1206, 1811, 1344, 531, 1399, 1850, 1846, 1140, 1429, 208, 1804, 971, 1168, 10, 332, 1152, 887, 1899, 1134, 1890, 169, 1144, 1507, 835, 93, 325, 597, 133, 754, 1641, 1479, 1306, 240, 1330, 1799, 693, 411, 1433, 1683, 1877, 126, 419, 698, 653, 781, 1620, 1381, 1181, 163, 1731, 1361, 1704, 1119, 212, 443, 119, 309, 673, 1860, 1694, 231, 262, 613, 638, 73, 1108, 982, 1712, 431, 1808, 205, 1896, 322, 1327, 416, 1728, 670, 1105, 1324, 1661, 546, 1664, 344, 768, 1737, 975, 1249, 291, 1391, 549, 1527, 500, 1609, 990, 830, 114, 286, 1667, 1559, 1091, 1654, 1172, 1754, 1471, 1061, 347, 1438, 1766, 1375, 868, 874, 809, 1449, 771, 737, 1602, 1082, 14, 301, 1672, 46, 1740, 585, 1831, 927, 1340, 1130, 1795, 1357, 978, 340, 1555, 733, 336, 1291, 175, 1536, 1252, 1688, 1825, 483, 799, 604, 1781, 572, 294, 1295, 369, 1367, 1156, 27, 1564, 905, 1394, 406, 426, 1649, 728, 844, 524, 1548, 552, 179, 1283, 849, 891, 389, 1423, 316, 1530, 1882, 817, 380, 82, 880, 565, 460, 503, 1540, 57, 1196, 1903, 789, 1096, 1231, 1612, 1001, 489, 356, 1634, 721, 1581, 272, 993, 1256, 1051, 529, 1138, 969, 1150, 1888, 833, 131, 1304, 691, 1875, 651, 1179, 1702, 117, 1692, 636, 1710, 1894, 1726, 1659, 766, 289, 498, 112, 1089, 1469, 1764, 807, 1600, 1670, 1829, 1793, 1553, 173, 1823, 1779, 367, 1562, 424, 522, 1281, 1421, 815, 563, 55, 1094, 487, 1579, 1049, 1148, 1302, 1177, 634, 1657, 110, 805, 1791, 1777, 520, 561, 1577, 1175, 803, 559, 557, 1511, 221, 1513, 823, 1757, 703, 223, 194, 625, 140, 1515, 467, 1474, 608, 825, 1125, 839, 716, 1759, 515, 1064, 1241, 705, 940, 1588, 1069, 225, 921, 350, 1785, 196, 184, 97, 39, 627, 680, 1441, 658, 142, 949, 1009, 1455, 1517, 1034, 1769, 576, 469, 1843, 329, 1504, 1476, 1680, 1378, 440, 610, 202, 1321, 1246, 827, 1751, 871, 298, 1127, 1288, 601, 24, 841, 386, 877, 786, 718, 966, 648, 1723, 1761, 1820, 812, 1299, 517, 218, 137, 713, 1066, 36, 1452, 1501, 1243, 21, 1720, 710, 707, 151, 774, 373, 942, 854, 758, 154, 1590, 1214, 740, 1625, 1071, 1164, 750, 777, 227, 666, 1605, 1371, 923, 479, 1645, 376, 352, 687, 1085, 1277, 1787, 190, 936, 945, 198, 962, 17, 1160, 186, 896, 1483, 857, 99, 88, 304, 1386, 41, 900, 1226, 761, 629, 510, 1675, 31, 682, 449, 1310, 157, 1443, 454, 49, 1028, 660, 1487, 279, 1593, 144, 65, 1743, 1568, 951, 394, 244, 1217, 1011, 1867, 588, 1186, 1457, 861, 1414, 743, 1519, 1493, 1834, 909, 1036, 256, 1334, 1628, 1771, 1315, 930, 1264, 578, 103, 1270, 1074, 471, 1205, 1343, 1398, 1845, 1428, 1803, 1167, 331, 886, 1133, 168, 1506, 92, 596, 753, 1478, 239, 1798, 410, 1682, 125, 697, 780, 1380, 162, 1360, 1118, 442, 308, 1859, 230, 612, 72, 981, 430, 204, 321, 415, 669, 1323, 545, 343, 1736, 1248, 1390, 1526, 1608, 829, 285, 1558, 1653, 1753, 1060, 1437, 1374, 873, 1448, 736, 1081, 300, 45, 584, 926, 1129, 1356, 339, 732, 1290, 1535, 1687, 482, 603, 571, 1294, 1366, 26, 904, 405, 1648, 843, 1547, 178, 848, 388, 315, 1881, 379, 879, 459, 1539, 1195, 788, 1230, 1000, 355, 720, 271, 1255, 528, 968, 1887, 130, 690, 650, 1701, 1691, 1709, 1725, 765, 497, 1088, 1763, 1599, 1828, 1552, 1822, 366, 423, 1280, 814, 54, 486, 1048, 1301, 633, 109, 1790, 519, 1576, 802, 556, 220, 822, 702, 193, 139, 466, 607, 1124, 715, 514, 1240, 939, 1068, 920, 1784, 183, 38, 679, 657, 948, 1454, 1033, 575, 1842, 1503, 1679, 439, 201, 1245, 1750, 297, 1287, 23, 385, 785, 965, 1722, 1819, 1298, 217, 712, 35, 1500, 20, 709, 150, 372, 853, 153, 1213, 1624, 1163, 776, 665, 1370, 478, 375, 686, 1276, 189, 944, 961, 1159, 895, 856, 87, 1385, 899, 760, 509, 30, 448, 156, 453, 1027, 1486, 1592, 64, 1567, 393, 1216, 1866, 1185, 860, 742, 1492, 908, 255, 1627, 1314, 1263, 102, 1073, 1204, 1397, 1427, 1166, 885, 167, 91, 752, 238, 409, 124, 779, 161, 1117, 307, 229, 71, 429, 320, 668, 544, 1735, 1389, 1607, 284, 1652, 1059, 1373, 1447, 1080, 44, 925, 1355, 731, 1534, 481, 570, 1365, 903, 1647, 1546, 847, 314, 378, 458, 1194, 1229, 354, 270, 527, 1886, 689, 1700, 1708, 764, 1087, 1598, 1551, 365, 1279, 53, 1047, 632, 1789, 1575, 555, 821, 192, 465, 1123, 513, 938, 919, 182, 678, 947, 1032, 1841, 1678, 200, 1749, 1286, 384, 964, 1818, 216, 34, 19, 149, 852, 1212, 1162, 664, 477, 685, 188, 960, 894, 86, 898, 508, 447, 452, 1485, 63, 392, 1865, 859, 1491, 254, 1313, 101, 1203, 1426, 884, 90, 237, 123, 160, 306, 70, 319, 543, 1388, 283, 1058, 1446, 43, 1354, 1533, 569, 902, 1545, 313, 457, 1228, 269, 1885, 1699, 763, 1597, 364, 52, 631, 1574, 820, 464, 512, 918, 677, 1031, 1677, 1748, 383, 1817, 33, 148, 1211, 663, 684, 959, 85, 507, 451, 62, 1864, 1490, 1312, 1202, 883, 236, 159, 69, 542, 282, 1445, 1353, 568, 1544, 456, 268, 1698, 1596, 51, 1573, 463, 917, 1030, 1747, 1816, 147, 662, 958, 506, 61, 1489, 1201, 235, 68, 281, 1352, 1543, 267, 1595, 1572, 916, 1746, 146, 957, 60, 1200, 67, 1351, 266, 1571, 1745, 956, 1199, 1350, 1570, 955, 1349, 954, 953])]