ans = [1, 1, 1, 1, 2, 1, 2, 2, 1, 2, 3, 3, 3, 3, 2, 2, 4, 4, 4, 4, 3, 4, 4, 5, 4, 4, 5, 7, 7, 4, 6, 5, 5, 8, 5, 4, 8, 8, 8, 7, 7, 6, 9, 10, 8, 7, 6, 8, 8, 10, 8, 9, 9, 11, 10, 8, 12, 13, 9, 9, 10, 9, 8, 10, 12, 10, 16, 13, 11, 14, 13, 12, 12, 13, 9, 12, 15, 14, 13, 10, 10, 17, 18, 15, 16, 13, 12, 15, 19, 16, 17, 12, 16, 20, 12, 16, 14, 17, 17, 12, 16, 20, 18, 17, 20, 22, 14, 17, 23, 19, 19, 17, 22, 18, 21, 20, 14, 20, 17, 15, 19, 24, 23, 22, 23, 22, 20, 19, 22, 27, 20, 18, 25, 28, 19, 23, 20, 24, 27, 17, 22, 26, 19, 15, 28, 27, 24, 24, 27, 28, 25, 24, 32, 29, 28, 24, 27, 28, 23, 21, 24, 33, 28, 24, 20, 30, 22, 24, 28, 28, 29, 28, 34, 33, 25, 29, 36, 38, 32, 23, 30, 30, 28, 29, 31, 32, 31, 24, 31, 39, 30, 24, 32, 35, 28, 24, 35, 43, 34, 27, 34, 41, 31, 34, 35, 36, 28, 32, 35, 37, 48, 26, 33, 44, 30, 33, 38, 44, 31, 31, 40, 25, 28, 31, 34, 46, 40, 36, 43, 48, 39, 29, 41, 43, 41, 35, 38, 51, 34, 32, 45, 44, 44, 37, 34, 50, 32, 30, 46, 45, 36, 30, 42, 51, 31, 31, 48, 53, 51, 36, 41, 45, 41, 40, 49, 49, 48, 40, 49, 46, 47, 38, 46, 55, 41, 43, 46, 47, 37, 42, 50, 52, 45, 35, 43, 54, 38, 39, 42, 49, 53, 42, 47, 62, 44, 45, 50, 67, 51, 34, 57, 63, 43, 42, 57, 58, 54, 42, 51, 57, 49, 35, 56, 56, 48, 48, 47, 57, 40, 40, 50, 60, 60, 36, 61, 60, 44, 49, 61, 68, 66, 47, 57, 67, 43, 51, 59, 61, 53, 44, 53, 69, 53, 47, 61, 72, 50, 45, 58, 62, 55, 48, 62, 62, 56, 52, 50, 62, 51, 43, 60, 71, 68, 51, 62, 75, 47, 50, 74, 69, 64, 50, 65, 73, 54, 60, 63, 61, 76, 47, 70, 72, 51, 50, 61, 90, 62, 59, 58, 70, 61, 39, 63, 75, 54, 58, 59, 74, 52, 40, 73, 81, 75, 54, 67, 84, 60, 59, 80, 79, 63, 53, 74, 85, 62, 59, 70, 84, 82, 49, 79, 74, 57, 68, 66, 68, 66, 58, 67, 80, 64, 56, 78, 78, 78, 61, 64, 80, 52, 50, 75, 93, 75, 61, 73, 90, 61, 63, 82, 88, 87, 57, 67, 91, 62, 72, 81, 91, 74, 60, 89, 82, 66, 61, 76, 97, 75, 56, 74, 93, 72, 56, 83, 98, 76, 65, 72, 87, 59, 53, 84, 74, 80, 52, 82, 105, 74, 68, 91, 97, 90, 68, 84, 85, 70, 82, 89, 107, 88, 61, 84, 97, 70, 66, 87, 95, 86, 71, 82, 95, 77, 64, 85, 99, 79, 74, 84, 104, 72, 64, 81, 85, 84, 67, 78, 106, 66, 61, 84, 104, 100, 79, 98, 103, 70, 80, 99, 106, 96, 69, 106, 99, 73, 73, 86, 108, 101, 70, 84, 101, 90, 59, 102, 120, 87, 80, 85, 108, 78, 69, 108, 105, 89, 72, 88, 114, 72, 75, 93, 100, 108, 61, 81, 107, 70, 70, 104, 125, 96, 76, 104, 119, 77, 79, 96, 123, 89, 79, 99, 111, 94, 76, 108, 115, 113, 86, 90, 115, 89, 76, 117, 108, 105, 89, 98, 124, 72, 77, 111, 103, 101, 78, 102, 109, 76, 86, 97, 113, 96, 73, 110, 114, 80, 81, 95, 127, 114, 82, 102, 113, 113, 78, 118, 129, 104, 92, 97, 129, 89, 92, 113, 126, 114, 81, 108, 141, 89, 81, 117, 133, 103, 74, 105, 123, 80, 93, 103, 127, 122, 78, 118, 123, 87, 83, 108, 150, 104, 69, 101, 117, 102, 80, 108, 118, 111, 94, 110, 139, 93, 89, 125, 130, 127, 89, 122, 142, 90, 92, 130, 121, 137, 87, 111, 146, 89, 103, 121, 120, 108, 89, 134, 134, 106, 83, 123, 150, 108, 96, 117, 128, 110, 95, 115, 137, 112, 106, 106, 137, 88, 79, 124, 138, 123, 94, 105, 121, 90, 90, 117, 149, 134, 88, 119, 155, 98, 108, 136, 159, 138, 92, 124, 140, 103, 94, 132, 151, 122, 110, 122, 154, 115, 86, 141, 139, 117, 104, 136, 147, 101, 84, 147, 138, 125, 97, 114, 157, 97, 97, 122, 144, 160, 92, 115, 145, 106, 104, 119, 138, 127, 85, 131, 153, 102, 97, 137, 172, 133, 100, 135, 149, 125, 105, 147, 156, 119, 122, 128, 153, 106, 98, 151, 153, 132, 104, 135, 178, 111, 103, 133, 155, 152, 94, 136, 152, 110, 115, 136, 164, 137, 116, 137, 148, 102, 100, 138, 173, 138, 101, 136, 147, 125, 100, 129, 159, 131, 109, 130, 154, 112, 91, 155, 154, 151, 113, 132, 174, 116, 113, 151, 163, 152, 101, 147, 168, 111, 141, 146, 175, 157, 101, 156, 156, 115, 110, 156, 178, 146, 109, 151, 179, 129, 110, 140, 173, 152, 123, 128, 166, 113, 101, 169, 160, 158, 102, 115, 190, 112, 106, 146, 175, 148, 107, 141, 179, 103, 120, 139, 167, 142, 85, 178, 169, 131, 122, 163, 189, 142, 116, 150, 182, 152, 109, 165, 190, 152, 132, 155, 192, 140, 108, 185, 168, 149, 123, 140, 174, 118, 130, 156, 165, 180, 119, 143, 173, 122, 138, 160, 175, 161, 117, 169, 176, 112, 110, 163, 206, 161, 117, 155, 169, 147, 110, 146, 174, 145, 134, 142, 163, 117, 111, 167, 195, 175, 139, 154, 211, 126, 123, 170, 187, 174, 118, 168, 208, 126, 146, 153, 198, 169, 118, 181, 188, 139, 117, 167, 202, 155, 123, 160, 199, 165, 111, 182, 185, 177, 139, 156, 195, 133, 123, 169, 206, 164, 119, 149, 215, 127, 119, 180, 180, 178, 115, 170, 186, 128, 127, 167, 189, 158, 119, 166, 190, 130, 109, 182, 214, 190, 139, 174, 196, 157, 127, 192, 213, 184, 168, 169, 187, 131, 124, 189, 198, 176, 129, 169, 249, 137, 135, 180, 199, 201, 122, 166, 201, 138, 153, 177, 212, 186, 127, 184, 196, 146, 130, 178, 230, 152, 130, 162, 190, 159, 154, 190, 183, 170, 145, 158, 193, 143, 130, 211, 206, 166, 128, 167, 230, 128, 131, 169, 219, 210, 129, 195, 221, 145, 159, 184, 218, 195, 131, 206, 202, 153, 141, 186, 225, 199, 149, 175, 207, 167, 131, 193, 214, 185, 153, 185, 214, 157, 132, 223, 233, 197, 142, 169, 239, 148, 136, 192, 210, 189, 127, 174, 235, 155, 151, 194, 213, 198, 136, 200, 223, 142, 158, 176, 233, 172, 120, 175, 204, 178, 128, 180, 219, 178, 148, 183, 240, 152, 137, 227, 228, 206, 151, 181, 254, 153, 147, 203, 235, 230, 140, 200, 221, 155, 167, 193, 244, 214, 162, 216, 228, 146, 152, 199, 256, 188, 149, 223, 199, 193, 139, 200, 219, 183, 164, 186, 242, 152, 143, 226, 217, 201, 151, 204, 251, 160, 151, 206, 211, 220, 136, 175, 227, 146, 189, 195, 225, 199, 135, 205, 200, 167, 139, 194, 271, 215, 158, 199, 258, 187, 143, 220, 247, 207, 187, 201, 252, 164, 155, 245, 237, 229, 156, 187, 275, 158, 136, 224, 239, 225, 165, 198, 264, 164, 173, 206, 231, 197, 147, 238, 237, 164, 151, 217, 291, 207, 153, 193, 247, 193, 132, 209, 259, 219, 186, 193, 242, 168, 142, 226, 228, 213, 147, 199, 259, 160, 173, 217, 237, 235, 145, 188, 235, 162, 158, 244, 267, 244, 154, 237, 243, 173, 164, 226, 282, 211, 164, 207, 268, 201, 163, 231, 251, 213, 187, 226, 251, 172, 159, 258, 261, 212, 188, 211, 260, 180, 163, 238, 238, 270, 159, 231, 263, 178, 188, 211, 276, 204, 160, 238, 246, 174, 164, 214, 286, 217, 163, 205, 266, 223, 161, 219, 235, 206, 182, 195, 267, 170, 177, 229, 250, 217, 152, 222, 277, 168, 163, 223, 262, 257, 168, 226, 286, 168, 198, 256, 278, 247, 160, 262, 263, 186, 173, 223, 305, 255, 163, 212, 258, 215, 172, 245, 286, 236, 209, 224, 290, 177, 158, 276, 253, 231, 164, 234, 292, 183, 173, 237, 268, 272, 168, 219, 272, 180, 201, 235, 268, 235, 160, 255, 258, 189, 167, 220, 314, 249, 164, 228, 262, 225, 180, 240, 276, 212, 179, 204, 263, 182, 157, 262, 287, 252, 161, 247, 316, 172, 174, 261, 298, 246, 177, 225, 300, 188, 208, 257, 293, 260, 168, 264, 272, 209, 191, 242, 306, 230, 212, 241, 284, 222, 172, 263, 266, 254, 210, 242, 300, 196, 174, 276, 279, 253, 176, 228, 335, 184, 176, 261, 276, 266, 179, 236, 291, 202, 215, 241, 269, 254, 171, 267, 295, 189, 201, 255, 322, 233, 173, 229, 263, 225, 163, 267, 273, 235, 216, 224, 244, 185, 168, 282, 300, 279, 191, 245, 336, 199, 190, 264, 319, 298, 179, 243, 291, 214, 221, 254, 286, 269, 206, 310, 319, 194, 181, 253, 339, 254, 213, 258, 304, 243, 173, 253, 305, 253, 216, 238, 309, 208, 171, 302, 303, 277, 190, 232, 336, 215, 187, 266, 277, 283, 175, 246, 317, 196, 241, 239, 323, 249, 175, 281, 285, 197, 182, 270, 336, 251, 182, 252, 306, 232, 154, 264, 316, 253, 209, 215, 307, 212, 168, 308, 323, 281, 198, 273, 350, 217, 202, 286, 324, 325, 215, 270, 316, 199, 236, 279, 299, 272, 188, 318, 309, 211, 203, 274, 327, 249, 194, 260, 301, 249, 195, 285, 340, 290, 229, 267, 311, 245, 194, 302, 301, 263, 190, 237, 368, 209, 226, 287, 309, 319, 203, 275, 293, 202, 221, 282, 319, 264, 202, 293, 329, 193, 196, 273, 333, 268, 192, 262, 306, 249, 197, 269, 327, 280, 226, 245, 297, 204, 192, 296, 326, 304, 241, 268, 384, 208, 209, 293, 314, 311, 196, 290, 325, 217, 243, 286, 355, 290, 198, 286, 344, 234, 211, 288, 396, 282, 201, 274, 331, 281, 190, 307, 320, 279, 229, 292, 330, 223, 227, 332, 332, 282, 192, 258, 374, 224, 209, 306, 355, 322, 197, 274, 329, 217, 232, 299, 337, 304, 173, 294, 320, 238, 213, 279, 374, 281, 199, 272, 304, 273, 203, 276, 332, 271, 263, 256, 350, 202, 195, 334, 317, 298, 178, 326, 395, 232, 215, 301, 319, 329, 221, 281, 364, 228, 255, 302, 349, 321, 220, 327, 349, 251, 220, 299, 382, 310, 217, 270, 353, 264, 233, 310, 372, 304, 249, 289, 328, 246, 212, 359, 335, 284, 215, 278, 407, 219, 229, 295, 355, 323, 208, 294, 346, 229, 252, 296, 364, 292, 214, 345, 320, 231, 212, 293, 371, 314, 260, 296, 352, 264, 199, 295, 326, 298, 253, 293, 369, 233, 206, 347, 347, 288, 211, 280, 365, 246, 202, 280, 374, 348, 220, 295, 376, 257, 246, 313, 347, 332, 235, 354, 363, 252, 255, 312, 414, 297, 223, 290, 344, 297, 213, 340, 369, 326, 269, 311, 380, 234, 214, 377, 373, 307, 238, 267, 396, 243, 223, 337, 361, 403, 209, 319, 355, 236, 255, 313, 380, 314, 239, 341, 359, 224, 228, 317, 412, 309, 215, 315, 384, 286, 234, 306, 378, 298, 249, 274, 386, 235, 213, 347, 342, 334, 220, 286, 438, 251, 190, 311, 342, 345, 214, 263, 371, 240, 267, 331, 400, 338, 233, 366, 355, 265, 241, 347, 438, 330, 240, 318, 370, 314, 229, 353, 400, 314, 289, 318, 404, 258, 234, 382, 351, 318, 252, 304, 421, 246, 234, 349, 396, 369, 254, 319, 376, 245, 276, 331, 358, 349, 216, 387, 390, 256, 242, 339, 429, 304, 234, 337, 358, 297, 236, 339, 386, 308, 285, 299, 378, 274, 223, 355, 352, 361, 229, 313, 422, 261, 272, 326, 359, 362, 223, 301, 356, 250, 286, 338, 389, 335, 228, 344, 375, 243, 245, 317, 464, 349, 244, 324, 414, 314, 239, 361, 431, 355, 275, 326, 380, 272, 239, 390, 412, 341, 275, 316, 447, 250, 239, 355, 387, 374, 234, 362, 402, 279, 294, 335, 423, 330, 232, 365, 401, 271, 236, 342, 471, 348, 243, 354, 391, 339, 237, 351, 382, 340, 287, 294, 416, 269, 277, 380, 398, 337, 230, 313, 444, 263, 243, 358, 404, 420, 232, 320, 435, 247, 280, 351, 389, 351, 227, 388, 412, 262, 237, 336, 445, 363, 228, 317, 362, 309, 231, 328, 392, 360, 289, 362, 421, 256, 260, 419, 392, 351, 265, 354, 457, 271, 268, 369, 416, 404, 250, 362, 442, 282, 291, 344, 419, 350, 252, 395, 432, 311, 252, 389, 464, 338, 258, 348, 422, 340, 285, 368, 422, 324, 293, 330, 396, 288, 252, 442, 413, 389, 276, 339, 483, 259, 256, 354, 405, 422, 267, 317, 379, 271, 309, 349, 435, 373, 245, 382, 384, 285, 236, 368, 507, 341, 293, 329, 440, 307, 249, 362, 381, 350, 294, 359, 420, 267, 246, 409, 423, 336, 249, 320, 455, 271, 251, 349, 444, 422, 260, 391, 459, 316, 307, 378, 412, 395, 258, 390, 435, 289, 315, 383, 488, 363, 275, 362, 408, 342, 249, 398, 446, 378, 316, 363, 445, 273, 246, 449, 439, 416, 266, 369, 499, 290, 282, 362, 431, 422, 257, 344, 413, 283, 296, 376, 407, 397, 290, 408, 464, 301, 254, 365, 494, 381, 260, 362, 435, 338, 256, 387, 445, 353, 331, 344, 462, 312, 236, 435, 436, 386, 265, 328, 485, 298, 254, 385, 401, 411, 250, 352, 442, 293, 337, 360, 440, 348, 263, 389, 418, 279, 241, 415, 530, 385, 280, 410, 456, 355, 268, 392, 468, 369, 312, 347, 470, 314, 272, 438, 475, 426, 276, 390, 511, 296, 299, 385, 452, 416, 309, 368, 461, 278, 327, 394, 418, 413, 269, 471, 448, 302, 276, 375, 540, 383, 271, 368, 440, 370, 266, 387, 477, 412, 333, 386, 442, 322, 277, 467, 415, 384, 282, 340, 529, 308, 315, 404, 464, 433, 259, 374, 421, 294, 333, 418, 452, 373, 279, 437, 437, 274, 269, 376, 488, 382, 282, 378, 439, 357, 262, 387, 458, 402, 312, 349, 420, 300, 269, 438, 482, 439, 330, 389, 530, 288, 294, 432, 442, 456, 277, 401, 515, 324, 358, 420, 499, 426, 258, 457, 455, 315, 293, 387, 527, 412, 286, 373, 488, 392, 310, 423, 465, 397, 325, 381, 491, 325, 315, 444, 463, 394, 279, 387, 524, 309, 290, 441, 494, 488, 262, 391, 492, 283, 329, 394, 522, 397, 273, 419, 491, 314, 290, 405, 519, 400, 273, 385, 439, 400, 275, 413, 483, 396, 370, 370, 475, 302, 260, 484, 443, 411, 304, 409, 558, 307, 275, 399, 489, 453, 251, 362, 465, 316, 325, 403, 499, 423, 284, 468, 485, 349, 296, 441, 539, 421, 304, 378, 503, 384, 333, 422, 501, 404, 343, 412, 467, 333, 289, 527, 479, 417, 305, 399, 550, 295, 303, 460, 484, 516, 295, 412, 494, 317, 370, 422, 511, 439, 289, 457, 460, 335, 298, 414, 549, 446, 343, 438, 505, 399, 284, 418, 453, 413, 346, 410, 488, 318, 298, 476, 486, 409, 309, 408, 584, 323, 312, 429, 493, 455, 297, 398, 523, 360, 356, 414, 452, 415, 291, 475, 474, 324, 341, 413, 579, 379, 307, 379, 450, 381, 284, 439, 496, 419, 358, 433, 465, 305, 283, 451, 510, 468, 309, 379, 597, 335, 313, 463, 509, 513, 306, 423, 508, 342, 361, 414, 534, 476, 349, 477, 524, 336, 285, 443, 573, 455, 301, 447, 530, 397, 303, 468, 517, 410, 366, 399, 529, 336, 321, 500, 538, 454, 304, 427, 601, 375, 305, 446, 471, 485, 305, 424, 526, 338, 382, 451, 520, 429, 289, 518, 479, 345, 292, 454, 554, 460, 326, 383, 511, 377, 295, 461, 534, 444, 365, 410, 520, 362, 278, 509, 519, 445, 301, 396, 574, 346, 298, 417, 510, 494, 355, 409, 518, 314, 346, 433, 481, 467, 295, 488, 489, 333, 288, 466, 628, 439, 328, 462, 529, 411, 316, 449, 553, 466, 387, 418, 594, 370, 313, 539, 495, 473, 330, 440, 589, 354, 367, 468, 545, 527, 309, 423, 493, 338, 377, 495, 575, 456, 323, 508, 528, 330, 352, 455, 588, 432, 301, 404, 524, 427, 340, 484, 546, 473, 377, 441, 492, 351, 310, 530, 552, 458, 366, 422, 625, 321, 321, 463, 511, 509, 319, 502, 534, 352, 395, 445, 536, 420, 314, 495, 532, 372, 324, 446, 600, 462, 324, 436, 528, 443, 301, 453, 478, 459, 376, 394, 534, 348, 351, 533, 530, 442, 313, 441, 569, 358, 318, 477, 542, 544, 323, 438, 566, 350, 383, 493, 548, 503, 312, 535, 598, 383, 348, 465, 639, 463, 335, 440, 512, 434, 328, 486, 561, 486, 441, 446, 559, 359, 343, 562, 523, 476, 330, 456, 636, 359, 353, 479, 560, 559, 312, 471, 553, 367, 384, 478, 572, 488, 321, 540, 546, 386, 332, 480, 625, 467, 306, 454, 582, 428, 382, 459, 580, 435, 398, 412, 513, 364, 316, 555, 562, 513, 328, 470, 623, 372, 315, 482, 569, 523, 309, 407, 581, 357, 392, 445, 556, 521, 329, 484, 508, 362, 334, 435, 663, 464, 374, 443, 553, 408, 304, 498, 511, 504, 352, 517, 610, 383, 356, 572, 604, 457, 346, 463, 659, 370, 344, 511, 546, 564, 341, 511, 597, 390, 398, 490, 535, 483, 338, 526, 573, 382, 399, 503, 705, 456, 347, 512, 529, 474, 354, 538, 583, 489, 412, 453, 582, 386, 332, 545, 557, 505, 342, 496, 650, 374, 334, 496, 564, 604, 334, 450, 539, 369, 436, 485, 579, 502, 387, 546, 581, 364, 346, 483, 634, 466, 354, 483, 540, 474, 341, 517, 544, 448, 406, 491, 587, 383, 328, 551, 568, 510, 392, 440, 665, 380, 337, 523, 520, 596, 331, 459, 611, 368, 439, 465, 585, 457, 330, 521, 499, 370, 335, 509, 697, 534, 364, 502, 629, 441, 342, 513, 598, 516, 424, 439, 617, 389, 351, 610, 610, 528, 373, 485, 663, 392, 364, 518, 594, 568, 392, 470, 627, 359, 416, 523, 566, 545, 362, 603, 610, 399, 349, 498, 672, 485, 345, 490, 614, 464, 336, 500, 612, 517, 433, 493, 604, 429, 346, 623, 578, 536, 351, 432, 684, 397, 407, 502, 601, 564, 339, 489, 563, 432, 406, 539, 625, 521, 342, 556, 601, 375, 344, 502, 706, 516, 379, 489, 592, 463, 339, 504, 617, 495, 413, 455, 551, 385, 338, 598, 583, 539, 394, 511, 664, 363, 324, 504, 541, 557, 345, 480, 611, 386, 399, 546, 661, 505, 357, 597, 607, 408, 377, 537, 685, 549, 377, 492, 635, 536, 371, 553, 589, 556, 423, 508, 623, 409, 441, 616, 618, 522, 363, 478, 678, 392, 376, 571, 624, 595, 383, 543, 645, 379, 443, 516, 624, 534, 384, 560, 609, 415, 377, 532, 716, 549, 371, 509, 562, 496, 352, 512, 650, 514, 474, 503, 647, 412, 364, 614, 567, 522, 368, 532, 702, 396, 376, 514, 615, 566, 387, 490, 637, 394, 428, 528, 634, 536, 365, 618, 618, 429, 365, 526, 682, 515, 362, 456, 604, 502, 415, 533, 564, 510, 421, 511, 596, 402, 347, 626, 621, 525, 361, 472, 720, 375, 382, 525, 652, 640, 367, 525, 664, 420, 479, 538, 657, 568, 364, 592, 586, 421, 414, 555, 750, 596, 434, 570, 646, 472, 371, 552, 600, 559, 447, 567, 627, 420, 376, 617, 642, 530, 374, 523, 721, 428, 383, 523, 707, 654, 370, 498, 609, 444, 440, 576, 605, 566, 366, 627, 636, 451, 431, 556, 734, 521, 383, 495, 592, 490, 369, 595, 675, 550, 475, 525, 683, 402, 358, 643, 623, 573, 368, 459, 784, 408, 378, 548, 640, 635, 365, 547, 598, 420, 451, 536, 658, 545, 412, 577, 649, 387, 375, 540, 707, 552, 376, 555, 649, 510, 366, 536, 662, 538, 401, 481, 636, 427, 363, 607, 647, 551, 346, 549, 782, 482, 427, 603, 604, 629, 385, 503, 699, 421, 537, 573, 687, 550, 382, 645, 606, 451, 417, 593, 751, 551, 409, 533, 673, 484, 386, 589, 677, 555, 474, 540, 676, 445, 403, 647, 688, 588, 384, 520, 727, 450, 386, 584, 659, 703, 442, 564, 696, 407, 453, 561, 614, 565, 410, 648, 673, 439, 421, 591, 746, 530, 396, 568, 663, 521, 362, 585, 659, 541, 473, 516, 672, 454, 379, 684, 597, 570, 408, 544, 721, 422, 449, 561, 651, 647, 417, 519, 623, 427, 452, 582, 648, 624, 391, 622, 653, 398, 392, 564, 757, 555, 393, 512, 661, 507, 406, 559, 706, 549, 473, 567, 592, 453, 375, 607, 699, 615, 468, 573, 779, 424, 404, 598, 636, 688, 394, 601, 707, 446, 496, 581, 732, 563, 393, 633, 680, 476, 405, 581, 789, 603, 430, 576, 700, 605, 382, 581, 639, 578, 484, 492, 726, 448, 450, 703, 701, 563, 431, 553, 770, 460, 397, 649, 677, 667, 411, 534, 701, 427, 473, 577, 711, 594, 392, 665, 687, 452, 400, 574, 789, 556, 404, 528, 670, 549, 367, 590, 740, 591, 530, 584, 697, 427, 381, 672, 624, 611, 400, 548, 843, 438, 409, 599, 709, 698, 392, 590, 689, 441, 497, 531, 658, 591, 389, 627, 698, 472, 394, 573, 752, 609, 412, 590, 655, 532, 441, 573, 689, 539, 468, 502, 625, 439, 352, 749, 744, 634, 428, 607, 840, 434, 429, 615, 717, 699, 406, 552, 709, 495, 504, 628, 715, 647, 406, 669, 661, 476, 426, 599, 806, 581, 507, 562, 742, 521, 414, 638, 654, 642, 489, 629, 710, 484, 425, 730, 734, 564, 419, 548, 817, 455, 438, 610, 693, 673, 422, 629, 722, 512, 506, 603, 645, 633, 410, 625, 713, 461, 494, 605, 808, 599, 414, 619, 650, 543, 415, 647, 722, 615, 533, 543, 719, 423, 439, 729, 708, 609, 422, 568, 837, 464, 422, 599, 742, 668, 405, 589, 644, 455, 483, 573, 719, 636, 458, 650, 694, 434, 423, 591, 789, 585, 425, 585, 691, 544, 415, 586, 729, 562, 489, 577, 687, 487, 411, 685, 742, 663, 443, 579, 852, 516, 433, 623, 680, 722, 455, 603, 747, 475, 565, 619, 750, 596, 419, 705, 679, 489, 430, 689, 872, 660, 427, 604, 764, 557, 432, 661, 765, 612, 506, 541, 767, 483, 453, 750, 743, 682, 401, 600, 809, 477, 426, 598, 742, 715, 471, 576, 724, 474, 517, 661, 685, 644, 404, 767, 759, 496, 457, 636, 844, 573, 431, 564, 716, 565, 447, 629, 743, 649, 506, 618, 741, 505, 424, 726, 672, 642, 424, 526, 843, 469, 491, 632, 740, 696, 420, 597, 676, 475, 514, 648, 784, 660, 401, 675, 739, 501, 417, 633, 821, 620, 418, 589, 738, 568, 424, 596, 748, 638, 494, 548, 685, 475, 412, 702, 766, 651, 480, 651, 891, 467, 441, 678, 700, 785, 446, 627, 793, 499, 540, 640, 783, 610, 461, 728, 815, 494, 452, 611, 869, 632, 468, 606, 731, 609, 433, 671, 689, 645, 543, 654, 766, 486, 502, 746, 752, 598, 454, 584, 837, 503, 484, 696, 753, 735, 448, 673, 796, 472, 523, 636, 751, 640, 443, 726, 768, 498, 442, 637, 895, 680, 445, 647, 687, 617, 433, 650, 794, 665, 607, 590, 775, 458, 432, 735, 676, 633, 441, 649, 862, 528, 502, 646, 744, 700, 429, 584, 763, 474, 515, 643, 788, 688, 474, 720, 757, 528, 431, 625, 827, 642, 438, 565, 762, 603, 478, 685, 752, 593, 518, 648, 702, 506, 442, 774, 747, 645, 458, 580, 820, 444, 438, 649, 785, 790, 462, 639, 806, 501, 552, 696, 771, 727, 451, 714, 721, 511, 472, 666, 914, 673, 524, 668, 796, 602, 477, 672, 739, 682, 558, 625, 813, 511, 450, 757, 778, 660, 459, 710, 899, 508, 440, 671, 828, 760, 480, 629, 814, 530, 516, 673, 766, 691, 452, 750, 779, 510, 526, 642, 962, 610, 447, 609, 734, 645, 450, 719, 780, 671, 545, 632, 825, 487, 446, 762, 764, 717, 496, 560, 903, 510, 436, 683, 778, 820, 445, 635, 720, 506, 532, 643, 785, 673, 523, 699, 825, 474, 487, 691, 859, 690, 454, 664, 808, 615, 420, 645, 781, 610, 549, 593, 808, 513, 439, 772, 752, 701, 456, 647, 953, 529, 413, 668, 715, 759, 430, 547, 798, 501, 627, 708, 854, 653, 457, 783, 734, 524, 493, 745, 947, 673, 486, 693, 804, 590, 459, 720, 818, 705, 558, 678, 840, 547, 472, 807, 834, 676, 495, 628, 881, 523, 480, 700, 807, 837, 549, 705, 818, 533, 548, 708, 735, 683, 456, 799, 760, 530, 477, 682, 945, 642, 525, 670, 779, 651, 460, 656, 820, 704, 575, 620, 812, 584, 465, 835, 723, 702, 476, 650, 934, 527, 554, 695, 831, 739, 451, 619, 789, 510, 582, 704, 828, 706, 495, 826, 775, 530, 465, 670, 961, 726, 456, 599, 802, 617, 486, 715, 827, 680, 547, 669, 742, 522, 528, 799, 797, 700, 539, 610, 903, 474, 494, 705, 703, 769, 446, 732, 832, 517, 571, 649, 832, 653, 453, 746, 767, 522, 471, 638, 957, 743, 494, 715, 860, 676, 487, 735, 805, 710, 568, 604, 878, 578, 544, 809, 866, 686, 484, 687, 915, 542, 476, 756, 849, 804, 512, 649, 852, 509, 570, 726, 859, 738, 469, 801, 856, 550, 535, 684, 965, 736, 500, 647, 764, 641, 488, 709, 848, 747, 649, 689, 877, 529, 481, 823, 765, 719, 471, 722, 954, 539, 485, 751, 849, 849, 474, 667, 815, 548, 564, 701, 849, 723, 471, 772, 894, 567, 521, 688, 917, 725, 453, 668, 858, 646, 533, 696, 872, 658, 554, 676, 757, 565, 475, 872, 828, 734, 504, 716, 950, 512, 473, 702, 827, 791, 439, 607, 837, 538, 594, 709, 849, 712, 471, 804, 758, 583, 467, 664, 984, 690, 556, 642, 830, 642, 481, 710, 774, 714, 557, 777, 910, 560, 500, 868, 831, 681, 497, 663, 985, 570, 511, 770, 878, 906, 506, 741, 873, 587, 619, 726, 799, 752, 517, 757, 905, 548, 578, 727, 990, 716, 518, 715, 770, 661, 494, 803, 883, 732, 604, 661, 876, 510, 471, 893, 881, 788, 547, 692, 1007, 544, 547, 703, 850, 856, 499, 674, 790, 547, 582, 716, 862, 770, 564, 853, 875, 543, 489, 760, 935, 712, 512, 701, 887, 655, 524, 728, 935, 665, 593, 706, 862, 553, 494, 807, 846, 725, 492, 665, 1022, 627, 493, 774, 774, 825, 500, 722, 806, 584, 673, 727, 853, 672, 531, 781, 785, 559, 492, 765, 1036, 749, 511, 707, 818, 622, 508, 759, 835, 713, 610, 620, 873, 551, 493, 840, 844, 771, 494, 743, 952, 559, 515, 724, 907, 880, 575, 708, 924, 545, 608, 751, 821, 807, 506, 893, 889, 589, 514, 741, 995, 705, 515, 677, 910, 689, 532, 771, 899, 775, 642, 733, 911, 611, 498, 854, 811, 807, 519, 687, 1035, 578, 577, 770, 891, 841, 509, 768, 817, 579, 610, 787, 912, 786, 531, 803, 929, 537, 507, 782, 999, 749, 521, 717, 894, 745, 513, 765, 892, 773, 609, 704, 823, 589, 490, 861, 886, 771, 623, 753, 1068, 524, 499, 743, 809, 865, 516, 722, 902, 571, 614, 789, 928, 711, 495, 823, 887, 600, 503, 723, 1051, 753, 535, 675, 919, 752, 494, 750, 818, 768, 599, 697, 891, 568, 567, 875, 911, 748, 504, 657, 969, 562, 536, 780, 904, 876, 501, 739, 904, 527, 598, 733, 901, 749, 496, 768, 877, 571, 488, 784, 1055, 764, 528, 819, 827, 712, 535, 742, 940, 775, 704, 708, 913, 560, 517, 912, 903, 812, 551, 814, 1058, 601, 546, 814, 946, 881, 516, 709, 924, 631, 640, 770, 915, 799, 532, 895, 914, 650, 526, 761, 993, 760, 567, 683, 930, 698, 599, 791, 949, 737, 669, 773, 833, 607, 511, 970, 935, 773, 569, 710, 1047, 559, 530, 806, 872, 926, 514, 769, 966, 586, 650, 758, 883, 790, 519, 860, 821, 579, 529, 772, 1053, 791, 599, 802, 901, 664, 524, 789, 850, 770, 632, 737, 873, 583, 589, 923, 907, 729, 528, 764, 1083, 605, 557, 727, 908, 939, 513, 745, 912, 606, 628, 749, 840, 825, 524, 869, 924, 582, 639, 751, 1013, 694, 518, 706, 820, 721, 519, 823, 893, 777, 629, 729, 906, 616, 516, 904, 948, 825, 551, 672, 1112, 603, 583, 823, 991, 940, 558, 777, 886, 588, 673, 787, 1005, 821, 593, 858, 941, 574, 537, 840, 1031, 826, 540, 868, 943, 726, 538, 784, 975, 763, 655, 716, 981, 606, 530, 937, 941, 828, 545, 766, 1119, 640, 567, 805, 861, 909, 551, 692, 967, 623, 725, 797, 964, 778, 499, 887, 844, 626, 580, 831, 1094, 826, 544, 769, 959, 713, 533, 849, 966, 797, 624, 782, 958, 625, 534, 933, 977, 811, 555, 695, 1040, 603, 548, 783, 970, 914, 622, 773, 987, 570, 635, 768, 872, 822, 521, 906, 941, 680, 540, 793, 1109, 743, 537, 771, 907, 734, 514, 799, 974, 784, 685, 710, 941, 639, 558, 926, 844, 836, 543, 730, 1074, 587, 623, 821, 943, 872, 479, 714, 848, 600, 630, 825, 960, 871, 500, 969, 1001, 597, 566, 858, 1085, 836, 574, 714, 1003, 730, 570, 854, 975, 913, 663, 842, 890, 634, 550, 911, 984, 864, 645, 743, 1133, 579, 602, 854, 873, 924, 558, 847, 979, 622, 713, 828, 978, 760, 568, 949, 930, 604, 559, 812, 1183, 833, 602, 832, 958, 822, 549, 816, 941, 803, 660, 725, 984, 640, 640, 978, 958, 770, 575, 822, 1052, 675, 556, 892, 953, 962, 571, 748, 987, 575, 677, 827, 957, 861, 594, 930, 988, 637, 586, 789, 1122, 799, 560, 738, 880, 733, 559, 834, 948, 846, 751, 798, 1020, 645, 544, 951]

n = int(input())

print(ans[n])