1000 14698 942
47 95 100 3 10 52 47 55 3 98 65 18 28 15 56 14 75 97 69 38 11 57 15 60 38 44 4 55 8 30 51 64 36 43 22 9 39 84 32 11 83 88 92 54 7 77 33 67 49 53 7 62 51 56 93 13 27 80 53 87 10 38 37 41 18 75 27 37 76 2 48 28 25 59 11 26 67 98 87 70 50 34 31 27 12 47 32 4 88 36 48 42 92 87 1 60 83 84 9 8 54 91 27 42 73 12 25 26 43 2 55 49 9 19 14 52 22 87 45 92 83 96 95 70 32 25 22 9 61 18 55 86 42 61 44 44 2 18 1 18 71 69 11 50 48 42 78 21 23 1 41 95 40 10 34 28 68 53 83 36 25 55 25 85 17 31 49 67 94 87 39 30 60 86 83 98 79 16 16 5 55 11 56 74 92 50 21 67 14 81 91 9 56 9 98 97 86 70 61 27 60 9 55 68 51 32 43 34 18 83 68 8 13 85 39 45 58 100 44 88 30 89 96 91 64 12 50 31 11 97 13 72 35 60 68 77 63 80 73 86 19 64 52 22 79 25 68 51 46 91 43 65 2 48 55 11 17 97 84 14 20 85 22 53 58 68 71 48 4 47 3 49 16 27 14 19 3 71 16 56 39 76 34 49 43 92 7 33 7 71 32 55 77 83 49 23 75 4 94 67 2 77 38 99 36 46 51 92 79 64 28 9 41 99 27 13 50 94 50 24 69 92 88 96 79 14 73 26 73 41 34 24 77 51 73 25 69 54 2 48 72 18 18 68 37 20 36 65 75 87 15 86 22 42 47 100 51 83 18 54 70 70 59 98 13 84 42 76 87 35 75 56 50 15 14 5 59 81 9 48 80 2 56 41 65 62 26 57 75 67 90 69 57 98 8 29 35 47 100 72 6 89 27 53 87 26 49 100 78 35 41 82 98 28 14 91 50 36 15 67 69 59 28 65 26 73 36 71 67 94 95 15 84 8 48 51 43 46 43 44 24 13 32 14 3 45 94 50 42 37 79 29 17 13 79 52 13 64 13 46 41 1 46 9 95 4 87 29 13 41 76 19 86 92 56 35 67 51 3 85 51 31 47 19 76 2 76 50 40 55 36 73 53 39 69 3 26 83 70 47 65 54 51 82 65 42 13 52 58 63 51 33 11 16 28 54 57 89 62 93 24 20 80 24 87 26 63 6 44 72 97 63 84 78 7 40 62 39 88 72 16 72 20 74 76 79 19 27 60 48 26 7 94 30 17 80 90 21 2 7 25 42 77 41 64 95 19 68 16 1 100 9 18 58 7 34 11 73 45 87 59 29 78 73 83 65 52 99 68 22 62 69 8 34 17 43 47 32 66 68 85 44 78 80 70 91 53 29 92 58 4 97 4 1 12 7 36 72 32 66 92 45 28 74 53 40 96 89 18 74 73 81 53 25 32 72 40 81 50 86 77 71 91 53 43 53 9 14 55 2 1 96 30 21 5 78 44 67 40 33 85 86 74 57 40 16 51 26 88 79 8 51 33 31 62 48 8 25 26 75 10 88 11 29 9 98 98 15 87 3 57 34 35 56 28 44 7 42 11 18 51 80 92 67 49 47 80 1 85 46 63 5 30 25 68 32 4 91 18 92 9 65 14 21 25 19 5 32 84 65 72 51 20 45 2 41 97 55 5 18 27 30 28 94 61 45 30 75 9 21 46 41 71 62 79 22 89 4 21 11 29 39 81 24 82 59 93 59 5 25 14 12 96 72 88 73 54 26 76 1 97 45 54 88 57 41 35 28 95 93 24 50 67 83 34 99 59 26 65 47 57 86 53 31 6 84 64 20 99 74 24 48 20 42 36 7 52 75 25 79 75 85 5 64 53 86 1 32 18 96 75 49 51 39 90 30 51 30 92 14 46 42 46 67 75 100 29 80 89 70 80 14 31 43 37 17 33 48 71 34 12 60 17 2 74 57 76 22 88 2 52 19 96 87 53 88 33 58 46 9 94 94 15 91 85 18 91 13 47 4 71 72 76 29 66 49 81 47 61 67 100 99 33 85 52 47 23 19 80 84 2 1 4 67 8 77 6 30 81 92 25 28 96 44 48 56 29 95 67 31 9 44 69 55 51 62 93 49 64 56 17 98 54 30 27 94 75 82 29 27 6 21 19 88 71 24 39 65 6 4 36 95 68 5 2 36 30 99 22 10 74 35 89 63 72 28 85 81 14 87 84 27 6 61 26 88 22 80 13 50 30 17 92 72 58 47 43 12 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1