题目描述
The test files to this problem were wrong during the contest. To make up for this mistake, the solutions submitted during the contest were rejudged with a time limit of 10 seconds after correcting the test files. Now that the test files have been corrected, the time limit for this problem is 2 seconds itself.
Teacher is explaining about a special class of sequences called the CFC (Climb Fall Climb) Sequence in the class :
" Say there are many mountains arranged one after the other and you are standing at some point of one of them. There are infinitely many mountains on your left and on your right. You start moving towards the right, climbing up and down, up and
down. On each side of every mountain, (K-1) villages exist. Apart from these villages, one village exists at the topmost tip of every mountain and one village exists at the intersection point of 2 consecutive mountains. Every time you enter a village, you note down its height from ground. As you visit more and more villages, you write down all these heights one beside the other from left to right. Once you are done visiting some villages, the sequence which you obtain is a CFC Sequence of order K. "
Note: No two villages on the same side of the mountain exist at the same height.
Here is an example for K = 3 (black dots are villages) :
Rani is listening very carefully to Teacher. She starts wondering : "Given a sequence < ai > of N positive integers, what is the length of the longest sub-sequence of this sequence which is also a CFC sequence of order K ? "
Input
The first line consist of T, the number of test cases. Then, 2T lines follow. The first line of each test case consists of two space separated integers N and K. The next line consists of N space separated integers ai.
Output
For every test case, print the answer to Rani's question on a new line.
Constraints
1 ≤ T ≤ 10
1 ≤ N ≤10^3
1 ≤ K ≤ 10
1 ≤ ai ≤ 10^3
Authors : Shreyans , Ravi
SAMPLE INPUT
2
10 1
1 2 1 2 1 2 1 2 1 2
10 2
1 2 1 2 1 2 1 2 1 2
SAMPLE OUTPUT
10
3
输入格式
见题面
输出格式
见题面
样例输入
10
1000 4
53 4 73 89 38 73 92 40 55 44 85 51 95 28 82 13 30 59 63 77 83 13 43 42 35 36 21 94 69 7 81 41 21 78 62 55 25 54 22 60 41 45 40 34 73 91 18 12 41 10 4 11 7 67 7 6 29 30 80 18 53 28 43 25 57 83 88 26 24 22 57 26 80 42 70 81 70 12 44 76 66 95 32 9 92 8 39 68 79 53 37 17 16 71 3 58 47 19 40 54 68 66 61 38 96 88 33 39 100 98 69 60 27 52 31 73 28 18 24 68 95 48 96 36 17 83 42 55 8 90 69 88 75 27 69 76 13 10 13 80 33 39 81 68 39 83 82 63 25 63 85 59 12 56 52 14 63 66 84 4 60 67 44 67 79 63 93 29 84 2 83 45 84 13 70 13 86 97 17 33 73 96 23 68 2 25 90 15 44 6 24 46 84 64 96 95 58 54 54 32 95 62 11 61 17 49 39 21 52 37 27 5 78 56 41 71 33 71 21 71 35 12 67 24 62 23 79 5 14 2 44 65 100 59 48 56 80 99 26 63 49 21 61 87 31 5 88 84 77 13 78 71 88 75 89 34 76 61 1 56 89 89 30 53 17 61 42 50 69 98 80 52 93 63 26 21 99 53 16 40 98 73 21 66 75 45 41 45 4 98 67 100 49 25 85 31 28 12 31 60 28 72 56 50 28 53 51 9 4 33 88 46 64 9 97 37 16 52 15 40 60 21 1 90 69 100 93 47 51 20 4 61 85 95 83 92 66 45 23 46 81 65 5 23 7 86 10 23 11 17 12 11 87 92 18 100 77 26 73 94 100 32 84 94 84 32 96 62 19 67 55 25 14 21 74 1 59 31 25 28 80 80 72 31 28 69 91 5 13 69 21 75 22 65 77 90 81 31 40 21 95 17 47 65 3 24 80 90 49 18 30 48 20 1 74 83 61 17 51 70 37 80 10 70 97 7 15 77 20 27 67 8 71 26 58 14 32 56 46 78 39 13 68 44 81 24 7 95 57 40 87 89 21 98 48 75 36 46 87 79 22 10 32 40 85 65 73 12 29 11 5 96 90 62 40 35 28 80 66 39 60 74 43 21 21 48 86 95 17 74 9 81 93 22 3 11 79 39 31 100 10 42 24 56 31 39 6 1 6 90 20 32 6 94 54 14 41 6 85 77 51 22 84 26 55 92 53 95 55 92 29 73 3 21 52 78 20 93 49 55 77 26 12 5 67 9 80 85 70 4 8 18 79 87 73 58 42 68 62 44 55 68 90 28 53 35 9 98 15 39 73 100 55 44 27 31 15 67 6 5 42 25 64 89 7 73 27 10 76 18 49 20 45 82 59 15 54 66 18 25 39 67 79 68 30 24 89 61 18 20 72 43 10 74 65 6 44 84 91 45 55 30 43 97 31 87 39 88 15 8 84 51 83 99 87 88 80 29 61 59 13 20 9 97 7 8 98 33 94 96 64 23 33 43 48 94 44 72 91 91 61 46 78 42 1 28 76 15 96 44 84 65 98 23 6 25 47 69 59 11 61 52 71 96 41 54 3 76 52 27 31 94 66 16 17 12 80 18 47 33 50 73 69 68 6 88 11 83 100 21 17 55 18 2 92 13 59 75 92 18 55 80 2 67 20 74 57 16 8 1 95 87 33 40 5 31 38 12 91 13 8 14 48 97 99 28 66 50 19 42 8 72 17 29 1 38 94 95 61 59 69 12 37 83 83 21 19 62 88 95 42 97 5 82 35 46 38 87 21 9 33 7 47 38 34 40 51 29 75 45 65 52 47 93 80 24 87 48 12 50 90 73 81 70 66 51 3 85 69 35 79 24 29 9 48 25 2 87 1 94 69 70 14 55 26 82 57 71 81 68 92 94 2 50 84 33 55 27 84 46 26 31 49 22 19 9 56 20 17 40 19 12 91 7 28 4 54 28 56 18 18 86 10 2 54 1 50 77 80 6 81 6 40 41 66 23 95 19 58 24 7 43 100 24 77 43 98 48 80 79 24 48 96 58 23 31 73 71 36 94 100 38 42 84 75 95 88 12 33 7 15 47 96 46 96 1 11 56 57 78 82 50 66 9 68 92 58 79 83 44 89 65 58 58 52 44 58 34 31 100 89 57 59 44 77 95 16 39 57 4 12 66 73 99 73 78 30 19 24 61 76 36 46 36 7 85 7 98 87 94 68 28 72 40 1 16 40 12 60 30 31 72 44 61 66 16 98 90 31 53 96 62 7 35 3 13 56 28 74 67
1000 9
18 95 26 100 86 53 41 75 51 19 95 29 92 41 90 35 62 84 77 33 96 63 52 70 64 11 32 25 83 94 50 56 20 67 28 83 69 9 42 4 5 74 17 64 20 98 57 26 1 64 68 50 37 16 42 49 53 14 20 18 30 50 60 48 82 29 22 35 22 62 55 49 69 28 72 30 96 20 15 77 100 94 14 76 52 56 57 66 96 13 37 19 68 31 16 89 89 16 26 30 96 51 24 60 45 46 65 4 47 14 23 98 97 89 99 53 32 91 63 6 30 64 99 33 86 37 54 36 29 21 22 82 65 54 74 27 63 12 95 79 87 64 21 28 98 85 68 75 95 68 10 53 55 50 23 42 25 35 86 75 62 27 86 93 83 55 77 97 32 5 59 97 82 32 94 2 12 80 60 16 7 12 90 27 46 76 16 12 75 37 1 31 79 7 16 14 95 83 43 90 92 89 75 16 53 12 5 62 87 23 75 67 89 82 2 45 80 38 46 57 52 32 2 89 49 29 82 73 1 1 98 86 55 94 97 74 71 12 26 75 71 29 74 32 49 19 62 17 2 22 82 43 22 44 1 67 73 12 7 86 81 19 81 1 1 97 36 93 98 45 77 9 51 27 16 35 79 98 30 97 94 7 47 49 3 40 91 87 85 68 12 48 75 82 5 15 13 73 1 44 12 99 23 68 49 12 49 12 26 4 43 59 76 59 29 2 69 93 39 27 93 3 80 6 70 49 29 40 80 19 91 14 46 1 71 48 91 30 89 83 92 97 16 85 70 39 44 16 78 87 93 41 43 75 55 85 11 77 93 88 26 54 70 5 52 51 42 18 38 53 9 16 27 8 77 86 34 94 5 82 42 41 14 76 13 68 73 94 94 41 45 3 43 92 31 100 2 95 99 40 22 47 80 95 72 45 62 69 98 65 47 76 27 87 37 43 88 27 71 61 35 83 46 61 63 97 25 67 87 79 18 43 78 29 31 20 18 21 56 80 24 15 7 22 52 26 10 60 20 47 8 58 2 51 67 71 49 67 100 22 21 95 55 59 44 14 52 40 47 92 86 26 17 1 44 28 20 38 62 2 33 53 40 10 86 74 60 39 75 47 32 61 98 40 7 49 62 99 1 17 89 18 61 79 44 30 14 14 56 38 95 13 19 93 52 87 61 48 54 39 43 47 90 32 7 53 53 71 41 79 58 68 98 69 28 79 15 43 37 21 72 19 60 5 73 70 23 78 21 48 20 9 30 63 9 32 48 79 13 19 65 36 97 86 76 56 83 98 40 96 26 67 32 80 18 18 97 45 61 20 51 19 10 55 15 19 13 3 48 38 56 52 14 10 60 50 15 61 34 40 100 8 20 89 19 94 75 60 89 69 67 64 83 16 89 11 48 90 91 6 17 89 25 57 11 98 11 51 29 9 34 5 79 52 56 72 70 76 14 71 90 55 72 45 4 100 28 15 79 16 94 86 85 33 44 28 77 24 44 35 49 99 46 66 29 59 96 82 78 12 31 92 39 66 32 81 91 6 15 66 97 54 31 33 69 45 13 84 8 63 81 25 22 67 11 85 73 86 34 68 17 31 67 57 86 95 36 71 5 11 47 32 94 92 76 21 5 74 13 13 32 20 73 60 89 31 79 99 73 12 21 31 83 67 5 39 73 22 31 95 92 31 98 45 98 1 95 72 17 8 99 67 17 54 1 98 38 40 52 5 23 6 74 18 94 100 9 7 89 54 93 16 84 89 23 69 5 82 19 60 80 78 76 66 63 50 68 78 49 57 6 33 56 64 68 88 52 9 88 59 86 84 58 16 71 17 51 36 82 90 37 4 92 52 55 26 77 48 42 84 81 84 91 81 8 37 75 91 47 55 93 1 88 35 27 90 91 21 96 74 2 6 100 40 99 11 96 99 100 47 55 20 55 61 41 75 50 98 60 86 53 2 56 28 54 48 27 47 38 79 41 11 5 65 56 55 6 39 67 65 80 35 32 6 39 5 36 13 92 82 50 49 66 52 18 71 86 58 79 81 58 43 22 75 67 64 46 83 32 27 85 72 29 93 56 43 21 40 58 54 12 78 33 72 36 56 34 32 78 58 66 33 16 42 16 58 68 87 72 7 55 44 9 68 34 25 44 77 13 97 13 22 91 33 61 31 98 64 68 70 3 63 32 27 99 75 10 53 23 77 65 91 69 61 76 66 49 90 34 77 75 45 8 77 81 52 11 82 71 37 97 13 33 46 17 71 13 51 41 82
1000 2
67 18 19 55 59 100 40 32 9 100 55 90 31 68 7 2 62 58 97 64 10 43 25 44 71 58 86 16 54 83 71 83 48 85 88 49 62 43 72 44 21 74 76 27 40 60 68 13 84 35 64 73 60 5 30 15 57 14 10 85 71 62 38 35 65 81 40 3 97 45 100 81 95 79 18 6 100 96 84 8 26 5 19 10 98 60 20 63 85 9 29 88 67 45 41 5 93 82 40 93 32 88 2 79 87 39 43 71 10 100 39 49 23 24 51 10 85 66 87 72 54 64 13 41 77 13 98 27 25 61 97 10 81 66 85 73 76 2 94 50 10 73 21 37 32 80 58 26 16 54 87 98 25 58 80 15 82 57 95 35 16 17 37 72 89 86 52 72 3 80 94 54 17 30 14 75 68 86 94 35 97 72 77 65 49 99 29 4 33 9 83 34 75 10 1 9 87 1 77 17 27 78 89 21 87 28 2 5 36 17 21 59 37 9 75 68 31 56 44 82 55 22 46 32 70 97 14 42 69 38 31 89 36 64 66 37 47 69 70 1 99 9 57 78 90 32 70 73 39 95 20 14 16 83 32 73 24 29 83 10 43 37 50 3 40 32 33 75 70 3 96 44 10 27 32 30 48 89 15 46 24 75 75 84 55 64 89 73 22 18 27 75 54 19 2 14 5 72 78 62 32 22 98 82 81 97 92 29 46 5 60 92 3 49 36 27 21 13 65 15 35 37 20 47 58 46 55 41 23 3 69 80 84 60 86 67 79 10 32 17 89 15 23 19 75 67 83 37 1 91 4 52 60 89 81 59 14 60 9 45 75 38 62 27 86 71 74 23 28 43 64 52 60 67 18 2 69 40 8 88 60 1 54 76 17 2 10 63 58 49 28 54 1 51 57 24 3 78 73 41 14 10 48 46 48 86 63 22 36 5 88 9 97 92 55 79 85 69 59 67 100 44 12 68 64 45 38 75 75 54 58 14 74 50 23 65 49 75 37 64 17 28 81 16 93 26 87 93 64 8 95 58 53 85 90 87 17 49 73 76 17 50 7 11 7 96 51 28 98 18 20 46 79 39 96 81 32 41 23 49 47 2 1 18 44 28 56 14 71 25 42 3 50 58 59 97 99 75 4 70 40 40 56 25 11 26 21 55 69 89 37 84 86 24 74 77 3 74 7 94 95 56 78 55 69 19 22 43 62 11 36 52 26 80 89 92 61 7 97 83 4 29 3 70 20 80 27 20 66 30 4 35 80 26 59 85 43 83 68 92 1 88 52 18 49 86 31 13 64 96 10 93 78 69 91 51 46 1 56 51 82 20 70 85 43 12 15 65 47 81 69 19 72 87 8 64 40 86 54 50 17 65 30 1 71 93 75 39 19 47 41 61 35 77 64 96 91 17 56 19 34 18 29 5 94 47 4 41 72 21 2 40 3 16 43 7 2 65 21 82 52 7 7 60 52 80 44 19 21 41 44 59 28 12 16 34 8 4 93 55 92 74 47 55 67 47 51 99 68 26 35 63 81 64 96 78 34 17 33 80 89 45 86 48 60 62 67 94 77 23 9 60 89 73 61 71 77 50 37 84 69 28 16 7 33 94 2 100 88 57 50 5 38 52 41 71 35 8 80 72 26 95 34 1 91 91 17 63 19 75 33 91 48 33 64 38 24 6 31 62 31 10 53 55 73 78 83 100 32 3 56 98 98 72 66 73 33 15 81 48 12 40 86 100 89 19 79 16 32 31 5 52 19 39 25 65 85 35 35 59 8 46 28 30 66 71 19 62 24 74 26 10 58 52 30 79 81 5 25 72 18 33 30 81 79 73 54 37 59 64 1 56 86 77 58 5 90 67 24 34 47 74 53 37 22 84 8 80 24 56 66 76 9 1 28 47 83 30 88 9 3 32 1 23 71 85 12 23 53 32 92 47 95 37 61 85 23 99 84 42 21 82 98 62 83 22 34 28 8 33 79 58 16 36 39 7 3 69 49 55 31 63 17 75 31 58 49 82 38 25 66 94 53 70 49 39 76 40 100 29 42 86 75 96 18 35 99 81 33 5 96 47 57 23 10 15 28 82 83 91 34 50 82 48 39 53 79 15 85 32 62 37 8 70 25 71 58 45 49 33 49 82 51 41 55 100 95 14 66 28 94 13 4 27 41 36 4 9 48 74 93 32 100 30 7 12 7 67 72 82 74 7 17 99 69 18 5 42 48 42 96 60 78 16 96 63 65 78 52 93 81 27 78 7 82 34 10 81 66 39
1000 7
87 36 62 74 68 42 98 9 98 57 85 47 55 94 8 17 66 95 45 90 5 36 31 5 14 56 30 34 27 83 80 56 99 84 84 31 45 94 100 66 71 30 20 86 4 40 97 63 5 88 31 66 90 35 74 65 7 18 54 35 44 100 82 55 82 15 39 42 63 81 50 26 98 88 7 22 35 7 30 55 7 78 46 70 39 100 48 71 1 48 26 4 72 59 9 47 61 7 16 99 37 91 42 66 73 65 94 70 96 87 88 73 96 23 23 99 20 21 17 30 40 6 22 13 57 2 97 92 27 22 23 3 88 44 5 53 22 50 80 87 8 73 92 84 93 21 45 24 78 81 77 36 97 37 65 40 65 3 81 35 60 70 55 30 19 60 7 43 29 44 55 36 6 19 27 13 9 94 86 22 4 67 99 9 35 99 73 66 100 69 3 16 5 9 62 91 10 23 84 54 9 29 89 90 35 14 88 80 20 5 100 80 34 97 52 26 18 2 44 18 80 36 37 30 1 82 74 11 85 18 44 56 70 6 79 25 17 14 2 56 95 5 68 56 16 54 80 23 35 68 31 94 67 43 32 62 16 45 48 53 49 27 94 45 48 92 100 28 22 40 32 73 33 92 86 50 7 54 59 87 1 39 41 66 36 92 67 55 10 37 24 54 81 99 15 42 7 14 58 92 30 74 15 88 26 81 70 36 47 13 4 71 64 2 68 15 40 86 100 78 8 80 94 89 73 15 91 90 76 19 67 48 63 6 87 45 95 32 24 95 14 75 33 78 97 60 22 93 73 93 81 54 62 13 73 79 98 21 6 58 43 5 69 41 59 14 56 79 54 93 39 49 2 88 32 73 67 35 4 63 14 78 7 100 50 52 95 47 71 63 48 38 86 47 22 14 66 84 97 55 49 56 24 94 50 96 26 43 6 62 66 57 12 7 70 20 14 2 78 63 16 52 44 45 19 5 71 60 42 99 60 20 52 97 8 66 6 11 75 33 70 57 80 89 1 77 38 9 89 77 95 96 42 96 87 52 13 23 15 7 57 34 59 83 94 77 8 75 31 42 74 11 80 88 37 36 24 52 43 24 39 46 5 96 96 6 77 58 37 57 40 58 26 75 15 12 3 66 59 72 32 95 25 68 83 3 83 61 33 29 92 8 25 57 22 83 74 24 82 16 50 47 16 90 78 97 84 62 71 25 84 83 57 79 62 57 56 34 48 58 29 34 90 62 98 75 76 84 80 89 6 38 76 49 36 54 48 44 93 45 47 91 58 5 35 35 58 49 34 61 17 31 55 61 86 77 74 78 21 72 35 5 56 27 99 35 8 43 20 60 36 66 78 50 10 13 41 33 25 9 49 12 62 61 99 36 21 6 62 64 27 55 98 80 10 7 32 57 100 88 22 53 47 21 36 40 20 52 91 47 39 92 29 68 6 100 30 85 18 53 69 75 18 16 78 50 14 32 50 88 27 30 27 31 27 29 26 47 92 9 50 76 15 11 63 87 27 75 23 30 60 17 91 73 76 79 93 84 53 7 21 42 27 48 18 35 16 31 75 73 77 81 89 91 7 1 98 78 55 19 70 61 6 50 93 32 96 78 74 16 46 31 10 21 22 31 24 35 54 95 43 1 20 67 96 26 1 92 14 2 39 75 72 1 49 2 26 78 61 50 26 15 51 25 8 75 57 7 51 4 52 44 83 94 46 80 36 16 90 97 84 29 51 24 40 2 17 70 78 18 12 42 39 13 58 4 67 2 27 11 85 79 60 58 41 38 37 100 48 57 2 26 39 85 79 53 66 52 46 53 58 8 69 7 8 75 1 70 4 48 50 52 22 26 60 46 96 60 57 86 88 17 100 11 11 41 66 63 18 35 35 96 41 52 12 40 77 99 42 83 94 11 28 49 36 51 9 68 17 8 64 34 52 24 86 75 89 84 10 22 77 35 57 46 27 38 68 7 67 83 17 28 41 70 51 91 81 84 94 11 70 10 28 18 17 42 30 99 24 84 57 41 34 36 25 29 12 2 90 20 41 86 100 49 78 85 25 9 21 59 45 52 14 10 11 47 6 31 73 19 64 92 44 5 94 54 45 5 57 96 47 92 79 3 97 9 100 32 83 44 30 75 92 26 74 100 23 80 84 19 23 62 49 12 26 73 35 69 69 52 45 20 92 83 33 96 90 1 27 70 36 40 30 27 1 90 96 89 33 71 93 99 63 48 84 24 13 78 19 62 15 39 25 90 72 20 72 88 25 36
1000 3
41 90 84 52 81 42 28 94 35 24 24 91 29 7 18 96 28 31 27 18 43 37 97 3 7 14 76 40 39 19 19 29 69 63 37 73 96 19 79 40 11 38 80 78 34 9 8 82 40 30 69 11 93 93 75 85 49 65 30 59 73 95 14 88 24 64 66 48 68 46 71 69 6 65 23 64 3 58 5 93 88 44 24 26 21 77 16 3 82 30 67 63 10 43 4 57 95 21 80 41 89 97 30 9 22 50 72 7 90 14 58 45 53 25 87 3 1 54 86 15 16 97 15 31 6 89 65 62 54 82 62 32 51 26 61 84 49 93 60 43 85 37 6 14 61 83 62 58 11 23 9 43 81 38 5 88 81 66 66 97 17 46 1 10 46 47 39 47 21 10 90 82 7 94 78 5 57 44 59 52 90 22 98 71 83 85 13 68 55 74 31 82 89 3 60 42 62 53 85 44 24 40 75 50 7 55 26 53 2 58 27 61 77 57 25 9 20 49 88 85 80 81 75 59 84 23 12 73 24 31 86 50 88 9 30 83 71 22 93 50 34 87 93 31 78 5 53 95 63 100 18 31 73 94 35 74 36 35 69 93 18 79 80 2 67 91 52 59 82 4 47 53 79 20 87 28 64 14 99 96 35 24 66 72 16 59 43 31 27 18 46 4 97 95 67 30 56 19 5 40 88 13 14 13 43 64 49 91 3 64 42 77 78 62 69 95 58 18 50 24 55 6 40 86 82 12 100 61 3 9 96 61 5 28 75 74 48 77 92 41 63 42 47 25 47 73 70 21 80 88 68 83 99 17 82 29 55 34 95 16 36 64 74 71 13 2 69 45 65 73 4 41 48 38 42 92 10 7 22 55 29 57 98 28 54 25 13 71 2 69 51 10 3 10 26 28 24 56 94 61 45 49 44 63 22 10 38 58 55 26 85 14 16 44 32 73 98 20 16 92 6 29 65 19 28 53 49 7 50 44 2 50 94 93 16 63 85 19 75 64 82 87 22 58 19 43 85 96 90 83 12 82 46 57 20 15 23 26 78 85 35 95 38 36 59 77 62 6 34 65 18 45 12 94 42 57 49 48 66 4 6 77 97 15 4 6 25 67 12 77 26 28 56 72 6 76 76 56 63 67 99 83 19 2 7 7 56 29 13 24 70 98 38 24 74 70 27 28 44 2 36 74 8 71 19 9 29 81 93 80 46 34 9 43 57 21 84 6 89 1 21 7 86 68 58 58 20 8 59 47 36 41 85 40 49 66 33 40 91 60 74 43 5 72 61 87 65 28 76 86 100 46 12 33 58 77 22 72 54 68 12 55 45 70 32 84 17 42 71 6 34 52 67 98 80 60 77 92 70 35 93 36 94 15 58 9 89 70 3 78 1 98 94 47 45 67 30 2 15 38 71 15 87 21 33 81 16 50 55 6 89 85 32 60 78 36 31 80 71 97 51 40 92 26 49 56 93 8 49 74 60 6 71 47 73 27 18 51 33 11 81 80 26 17 38 50 37 17 3 95 89 65 39 73 68 25 49 18 80 59 43 36 35 75 74 49 2 91 15 86 90 22 17 100 48 98 38 50 31 11 75 35 51 74 84 51 8 46 2 37 44 18 11 8 37 52 83 74 46 32 33 80 56 3 50 56 8 53 39 91 87 45 81 87 20 25 84 28 69 18 80 89 21 76 4 33 70 57 64 79 98 58 98 86 70 59 35 41 85 72 35 90 82 64 90 42 85 73 92 49 11 11 56 86 100 22 56 36 73 54 20 86 42 10 84 40 17 33 94 87 47 7 65 19 91 18 35 59 61 38 5 9 69 47 96 7 64 67 46 65 30 84 47 55 85 55 13 30 16 49 78 58 24 68 85 2 39 73 46 67 49 5 70 26 20 22 6 37 51 23 74 56 34 2 45 20 28 21 23 67 32 43 7 89 98 29 99 15 49 73 56 66 45 13 50 34 47 42 52 32 90 59 16 93 13 5 10 47 58 33 37 81 37 96 65 22 9 25 63 22 26 100 94 24 32 2 91 91 75 61 36 48 67 41 36 83 74 36 70 74 56 42 23 18 6 99 68 63 90 85 77 38 10 24 55 49 19 37 20 71 67 43 56 12 26 96 78 87 62 83 57 7 25 28 32 83 60 57 33 93 29 67 29 68 84 89 66 12 73 44 13 71 64 30 78 54 35 13 66 17 64 46 27 90 62 99 34 31 22 81 6 92 41 25 51 100 72 13 89 94 15 82 30 38 10 76 33 8 52 42
1000 2
73 73 34 45 69 83 24 12 4 93 67 100 79 63 71 27 78 72 66 15 11 28 64 79 42 60 12 81 11 28 26 5 7 25 38 97 63 99 2 30 28 12 51 95 8 86 48 90 29 53 23 36 11 81 36 48 69 7 51 54 35 65 73 83 90 91 90 76 87 75 90 4 21 96 82 36 5 99 60 86 71 62 9 40 86 37 73 77 28 18 76 76 87 64 16 71 84 23 3 39 34 2 11 31 81 65 55 65 63 41 3 44 38 17 23 19 56 49 7 22 47 70 91 43 85 44 86 74 31 10 100 8 96 61 45 21 64 14 74 28 46 13 6 45 51 78 13 93 84 25 3 51 74 10 4 79 7 17 39 74 32 16 81 69 1 23 68 39 12 11 56 96 21 38 24 83 86 14 99 50 67 100 84 53 8 63 72 8 6 85 60 45 34 76 27 45 12 17 21 25 15 70 96 44 94 65 37 68 70 97 54 74 37 31 3 26 71 24 30 54 38 74 96 70 47 71 29 83 2 31 35 76 91 72 34 46 35 30 26 59 85 10 89 85 66 65 38 24 37 66 55 5 27 100 23 80 25 17 55 73 8 8 38 62 38 76 54 5 89 96 25 63 65 73 28 68 93 43 99 9 63 33 38 50 68 4 42 61 81 9 86 62 35 12 87 45 9 79 85 93 36 16 41 38 31 52 76 69 28 92 58 99 64 12 47 75 26 86 20 76 11 11 81 66 98 72 65 28 43 24 2 46 92 65 31 91 23 17 12 74 17 1 77 24 42 60 62 33 70 97 13 73 99 32 76 1 44 36 16 66 70 21 90 100 9 12 53 74 1 76 96 61 41 14 50 30 79 12 40 9 2 53 45 48 81 20 19 79 88 7 85 33 64 90 12 87 42 81 58 27 12 82 33 44 88 98 64 80 17 41 52 54 62 24 97 45 48 30 71 80 19 86 35 12 94 61 44 43 52 87 95 2 90 62 38 1 45 78 36 18 14 30 10 47 96 67 12 92 9 23 3 48 61 57 66 75 12 67 70 64 99 34 35 67 53 13 3 78 6 37 77 68 15 68 74 6 50 5 31 65 29 2 64 95 74 67 2 1 90 87 59 50 83 55 82 6 42 43 1 50 97 48 23 41 51 15 49 78 73 8 16 56 21 80 80 98 22 48 28 96 51 66 50 29 3 2 100 88 49 99 15 60 51 42 43 63 44 10 15 42 53 44 34 6 56 5 25 95 68 61 59 40 77 31 100 66 1 18 82 23 53 2 73 82 36 40 31 38 28 30 66 76 46 2 70 5 57 4 83 63 86 58 72 63 62 12 39 87 15 40 79 12 19 47 48 91 55 53 45 56 96 58 40 59 44 30 10 90 63 74 80 75 78 42 2 46 27 13 45 86 90 60 75 36 100 71 22 59 50 18 69 22 60 55 52 99 10 63 33 18 71 90 26 1 89 46 49 17 8 47 74 89 6 93 79 21 34 50 94 22 31 95 14 88 84 16 99 40 10 66 79 91 97 28 69 15 30 25 5 56 96 66 24 54 83 79 62 81 46 67 1 20 47 99 56 58 83 86 51 55 78 22 85 63 41 14 7 84 51 24 27 24 69 65 9 72 4 83 24 6 79 46 65 22 46 71 63 85 63 40 26 50 87 40 46 65 90 74 14 43 2 47 30 27 89 77 84 30 62 61 26 42 67 20 81 94 16 10 100 99 14 71 20 30 44 55 54 16 22 8 42 30 40 53 90 27 41 9 18 54 49 56 23 12 92 61 89 5 81 73 90 86 45 3 40 35 63 24 29 50 27 93 21 76 89 27 84 94 61 10 22 27 29 5 99 24 91 48 78 88 64 3 21 76 19 7 70 2 22 95 52 46 22 81 29 81 9 76 43 54 73 71 20 5 34 67 98 98 24 2 43 73 30 73 42 51 22 92 6 65 42 39 66 36 38 27 49 41 100 32 95 45 84 53 49 72 68 27 97 41 99 83 28 94 79 43 60 74 52 9 57 26 75 52 76 32 97 95 82 56 93 21 33 53 92 96 87 80 34 92 27 39 79 94 22 45 79 96 15 88 3 47 42 51 45 56 45 62 6 59 70 86 93 85 7 17 79 7 28 9 9 95 53 64 49 7 20 56 2 40 39 23 13 5 25 42 48 24 69 70 56 96 68 27 76 64 32 53 14 7 8 11 5 24 66 66 78 75 2 85 23 13 25 54 47 56 14 62 11 27 68 16 96 61 41 39 82 51 13 97
1000 2
55 74 66 38 26 18 78 88 54 21 30 87 64 96 41 52 12 98 74 35 23 95 76 90 80 67 83 95 34 88 97 35 84 86 23 24 38 89 52 55 39 12 82 10 80 69 92 30 92 9 44 24 60 57 6 89 85 1 49 26 52 88 21 25 65 48 56 86 87 88 84 9 3 51 97 76 63 55 95 3 57 21 31 18 11 31 15 3 21 11 62 1 73 38 49 36 83 9 47 49 58 54 91 32 25 62 99 73 73 94 90 12 42 56 63 25 40 47 21 54 36 42 79 70 55 92 45 70 90 64 70 5 94 15 35 25 90 78 44 24 63 86 34 85 56 49 100 24 34 71 66 55 85 17 86 62 43 1 21 79 49 49 71 54 60 68 62 76 25 46 88 59 13 96 93 70 46 77 34 32 6 27 100 38 33 36 73 72 12 38 5 73 96 17 56 28 48 32 98 29 63 23 83 72 18 47 56 98 37 94 57 33 23 97 61 87 15 80 59 98 56 9 74 78 40 95 99 98 37 91 89 44 12 44 49 64 7 92 24 27 92 3 58 51 78 31 31 5 12 40 63 10 59 49 22 8 1 55 39 37 31 54 26 68 87 21 6 6 91 9 47 95 16 13 91 42 22 37 80 54 7 52 35 45 2 82 23 97 3 50 15 22 28 28 84 3 45 46 3 4 43 76 90 95 21 50 45 1 28 49 55 40 93 28 62 11 17 1 99 98 8 6 97 66 45 81 53 35 13 24 22 68 94 29 38 6 90 49 9 62 28 33 88 64 38 61 56 20 95 89 60 82 59 2 56 52 61 6 72 73 96 66 13 11 97 98 86 98 52 54 33 55 77 16 27 74 49 22 65 20 53 90 25 11 66 19 60 99 73 62 65 8 5 68 22 81 96 77 13 53 38 26 3 21 88 83 100 41 71 92 5 26 94 13 65 31 53 23 9 62 76 97 32 90 57 31 31 98 58 21 49 81 25 100 33 32 96 53 87 55 95 30 88 27 19 24 34 39 46 21 71 34 16 95 29 49 80 6 50 18 75 11 5 36 92 88 77 99 62 66 80 26 50 8 58 47 11 90 35 55 78 33 10 11 65 61 56 74 37 85 25 64 64 58 73 67 96 51 13 4 5 62 23 83 39 42 59 14 83 64 84 19 95 92 91 57 89 98 65 37 69 41 99 34 65 2 29 5 65 59 23 61 98 42 40 10 71 25 68 88 39 4 81 54 77 5 44 40 37 70 20 30 91 88 80 58 42 7 65 68 70 27 86 23 76 65 7 75 97 64 91 4 34 53 42 74 84 29 98 99 92 70 74 65 24 57 43 68 13 38 53 94 20 48 82 82 92 23 81 65 10 7 6 31 21 56 31 73 11 26 14 7 19 17 21 41 27 85 94 74 61 50 49 8 2 28 87 29 30 65 64 25 42 19 15 10 39 83 96 40 30 10 86 44 45 28 75 11 73 58 8 47 84 28 25 54 5 82 77 94 57 6 82 83 32 71 28 14 53 32 65 43 86 69 8 22 84 9 98 47 37 71 21 30 79 51 1 64 64 39 28 7 38 50 33 87 93 15 11 90 50 99 51 73 67 1 34 25 44 2 36 5 36 65 38 4 93 59 46 21 84 1 48 41 88 34 7 5 80 80 70 21 11 35 12 44 32 52 26 40 90 39 79 65 62 22 93 21 2 88 78 63 12 91 9 64 20 89 2 25 86 41 8 90 4 92 93 14 14 46 3 93 10 78 41 90 78 76 55 1 4 35 99 12 69 66 52 20 65 71 36 54 82 50 56 86 56 46 51 4 56 49 89 74 47 77 77 65 57 67 60 31 20 27 23 45 51 36 79 52 48 69 44 53 9 72 52 69 83 6 60 50 39 75 4 80 6 19 26 94 46 14 73 41 65 48 84 93 93 84 63 41 17 62 70 70 51 14 91 31 30 71 10 40 18 47 99 10 46 85 14 1 98 49 24 57 41 47 60 38 4 74 37 76 11 94 14 73 31 96 41 4 61 1 72 17 58 2 96 70 52 78 44 30 8 80 47 48 8 35 49 50 67 15 71 38 91 1 88 46 14 50 62 55 63 56 1 79 63 50 10 94 64 2 4 77 9 96 36 14 19 48 62 51 75 90 31 54 44 84 20 64 39 53 54 89 53 21 99 40 8 54 26 95 81 85 30 25 13 28 21 26 82 18 95 83 23 99 16 19 15 34 54 52 51 92 41 78 67 8 53 37 14 15 58 49 23 52 6 11
1000 9
52 97 98 28 42 56 43 20 51 25 28 3 76 82 26 69 68 88 34 64 91 63 89 72 47 87 40 7 90 1 23 91 24 87 36 50 39 4 10 42 97 56 14 1 57 48 82 54 23 17 37 64 8 13 42 83 77 61 52 1 12 29 73 54 45 21 57 59 94 81 90 44 5 4 49 92 57 8 76 42 47 21 34 44 22 67 54 86 41 93 4 100 92 91 20 28 91 22 13 28 18 11 33 87 83 97 5 81 80 3 75 72 40 93 46 36 26 41 43 62 92 57 57 89 36 68 82 21 52 14 24 85 83 64 84 38 88 31 90 32 63 87 77 60 12 87 97 63 6 31 7 99 53 35 71 43 8 54 93 87 62 17 81 81 93 97 35 38 51 30 83 32 33 65 56 63 57 25 79 74 12 17 34 60 64 65 10 95 34 31 10 53 68 55 45 92 9 78 2 70 17 54 70 94 82 58 13 77 7 29 52 40 88 60 34 81 42 25 74 69 4 25 5 53 58 48 80 56 22 95 84 59 9 27 65 85 95 33 31 41 40 85 52 90 37 70 65 71 82 53 66 12 66 14 41 60 69 48 86 58 16 49 3 32 59 73 93 66 51 9 16 64 50 12 10 44 27 41 9 82 56 91 96 29 62 88 32 57 80 76 67 84 76 22 65 30 47 80 9 52 26 20 58 34 72 93 99 45 50 79 64 37 17 42 70 47 2 25 80 64 84 78 63 70 5 84 63 29 30 5 79 52 56 49 34 74 19 14 95 94 31 10 19 37 92 78 37 86 50 12 70 15 83 39 81 16 43 45 44 48 43 30 65 30 6 92 76 52 50 22 42 82 53 72 45 86 57 67 44 92 68 25 78 75 23 8 2 37 55 7 42 16 98 45 68 73 68 96 100 41 1 33 19 26 96 55 36 31 28 13 13 63 82 16 64 91 100 99 10 13 32 81 7 28 88 32 60 30 96 27 78 25 89 27 80 29 64 62 38 24 38 16 30 91 7 57 7 49 48 26 89 45 62 94 81 97 48 77 13 100 40 60 97 55 4 48 11 24 62 12 16 30 62 8 25 89 24 68 41 37 85 99 63 93 30 60 54 34 58 94 6 48 43 92 3 64 20 44 1 62 86 43 90 81 85 89 56 33 7 49 52 92 3 64 87 4 43 70 7 28 79 33 85 21 9 97 90 19 85 92 78 24 26 70 32 88 5 91 55 50 26 84 13 86 40 64 26 19 41 100 3 11 46 73 100 64 7 100 74 97 94 98 6 78 68 61 65 32 32 43 92 29 45 9 84 98 14 7 76 1 92 42 96 50 75 94 4 8 64 9 93 18 51 7 16 47 95 32 3 5 22 39 37 45 55 37 8 17 52 69 41 39 89 68 88 58 58 76 53 42 69 49 2 37 40 92 45 83 48 47 76 70 38 8 100 3 44 98 87 6 27 21 89 45 91 2 40 50 36 26 74 46 72 22 8 22 90 59 33 60 29 18 69 31 24 79 55 58 60 41 71 66 90 5 63 86 15 81 28 87 88 58 29 59 87 85 40 79 8 14 56 7 40 78 86 69 36 42 18 95 12 95 65 41 69 93 41 22 71 91 16 32 79 12 16 42 22 7 14 85 10 59 26 15 73 1 18 36 74 91 75 21 39 34 29 46 4 19 33 6 37 69 55 62 80 62 72 46 43 75 30 99 61 68 90 62 83 48 43 59 83 81 77 34 73 56 6 41 16 20 60 10 81 100 83 88 7 49 69 16 16 88 11 78 68 8 2 16 86 32 23 71 55 67 47 87 43 68 62 91 100 32 74 65 98 50 22 31 88 77 47 84 65 64 31 93 83 10 16 38 26 39 75 79 52 7 46 26 35 62 79 68 65 55 62 28 48 4 49 87 100 87 85 73 76 70 16 86 70 80 57 48 44 15 71 68 92 88 70 87 4 9 62 83 29 22 21 79 51 91 27 91 26 45 65 31 31 86 47 73 38 13 53 17 70 46 31 25 62 94 19 97 91 35 3 93 58 31 48 53 55 94 42 20 94 88 69 31 5 75 92 80 74 9 67 46 39 38 34 47 67 45 28 73 38 11 10 90 28 48 37 10 69 8 92 89 49 53 54 37 3 51 38 36 75 64 69 22 36 46 74 6 86 25 71 23 80 89 14 9 57 67 60 3 33 79 3 91 6 38 7 32 56 77 91 79 52 74 93 62 83 6 1 77 11 18 22 78 46 41 64 90 79 18 23 8 9 34 49 89
1000 3
77 94 29 92 61 77 57 25 67 48 33 23 1 84 81 10 4 94 94 27 83 33 86 5 96 100 56 27 17 27 88 71 69 73 95 99 64 9 22 94 4 78 32 1 69 10 41 100 68 66 84 75 51 7 53 56 92 5 4 42 52 48 4 39 42 14 55 94 28 87 33 4 11 62 43 52 93 57 26 40 52 28 52 38 94 62 54 31 68 16 99 3 47 86 20 69 59 19 57 88 10 62 26 42 13 50 9 4 69 51 7 66 37 30 93 25 10 28 26 42 47 54 46 57 94 59 64 73 50 60 76 21 82 76 74 8 35 60 63 53 81 74 33 63 36 66 24 7 80 55 16 46 85 38 72 76 97 76 38 4 10 15 40 94 69 51 29 83 31 17 28 52 58 28 60 22 23 62 89 80 69 76 9 41 6 26 98 60 44 65 83 29 63 63 38 2 73 100 78 22 59 13 53 48 78 65 15 51 76 15 51 73 87 47 64 42 30 80 100 6 39 6 50 25 69 51 82 37 48 23 18 93 37 76 41 54 38 95 66 31 1 60 70 73 64 44 50 38 45 29 77 73 35 66 61 83 53 32 39 16 96 36 20 9 55 5 57 4 14 76 94 25 8 35 91 28 75 27 7 99 71 73 22 77 66 67 44 67 37 94 70 86 3 10 29 61 96 2 85 36 99 58 79 5 68 78 54 51 79 43 82 36 93 84 46 35 50 15 40 57 42 64 91 23 36 39 96 17 11 5 36 74 99 39 48 56 53 66 86 13 86 30 100 9 93 33 26 54 85 3 93 78 92 68 9 96 75 97 14 26 18 55 10 8 76 40 66 41 66 47 8 82 51 70 56 87 88 98 21 2 21 10 54 97 40 72 56 4 51 49 19 79 32 64 100 24 65 32 5 100 45 69 95 18 14 40 19 85 27 57 52 48 88 6 84 94 36 9 85 71 82 47 14 80 69 79 54 98 57 77 12 85 25 83 16 14 63 67 68 27 24 27 99 47 32 5 82 94 34 51 80 85 95 58 47 9 41 86 12 72 22 21 39 93 6 15 26 53 2 97 88 86 61 60 93 23 16 85 57 32 16 6 72 95 34 8 44 95 28 3 68 48 79 93 83 99 88 55 10 16 51 96 3 77 12 11 95 25 84 68 88 56 100 82 58 12 95 39 30 73 42 55 45 21 32 49 44 24 4 64 72 42 78 85 80 24 59 6 52 96 28 67 100 91 33 94 89 9 87 48 44 28 60 2 21 52 96 61 65 99 16 10 75 67 99 36 59 36 9 39 73 8 23 81 21 76 94 91 38 49 100 83 28 86 56 39 96 24 73 85 95 32 57 92 40 23 50 9 54 28 74 43 21 61 63 28 86 23 65 29 73 96 43 48 66 53 7 36 31 85 78 32 26 11 88 16 78 3 11 16 86 60 58 18 17 84 20 78 7 61 57 60 49 6 40 98 83 13 22 59 42 11 44 3 20 69 71 56 90 58 47 20 50 72 5 36 4 68 48 92 70 60 46 48 46 96 28 74 47 92 71 49 36 7 81 14 84 17 31 57 67 4 4 10 16 49 19 36 55 62 20 46 64 39 44 84 37 45 29 73 61 100 60 82 10 4 54 37 28 75 29 99 62 18 12 90 92 86 4 63 94 12 56 4 56 55 59 69 14 93 81 8 6 21 27 70 20 63 39 96 73 12 56 65 79 71 13 84 63 24 32 34 4 60 92 17 20 50 31 8 96 45 34 82 37 49 10 28 76 70 33 66 78 71 35 77 49 63 37 4 21 14 71 95 94 10 81 23 68 7 69 34 28 28 90 82 15 94 76 74 85 11 42 80 44 76 24 57 60 87 91 13 97 20 57 66 95 88 53 44 89 54 75 94 10 34 100 83 7 7 92 30 37 62 60 54 46 27 10 66 94 66 66 64 28 50 90 41 64 88 94 57 79 32 22 63 29 84 95 78 58 85 60 89 85 61 25 92 65 5 81 100 48 84 4 94 29 89 3 42 44 66 34 26 37 92 14 56 69 24 25 83 84 71 79 42 68 78 63 82 92 33 89 59 53 86 60 92 21 4 62 66 40 32 55 66 8 98 20 90 3 33 85 30 8 85 13 23 19 41 76 67 88 48 54 10 90 10 38 69 95 35 97 81 80 32 20 15 75 59 74 21 91 44 23 7 95 92 26 98 29 72 54 77 25 93 24 63 2 63 94 24 56 71 38 87 15 70 72 59 95 58 10 73 20 27 67 85 16 66
1000 6
73 43 93 100 62 14 64 19 88 87 2 64 36 43 43 47 92 85 76 41 11 67 59 27 37 35 73 93 93 84 65 69 86 32 79 98 23 40 61 19 2 2 21 64 10 74 95 19 35 60 48 70 63 96 75 24 47 3 39 61 75 86 53 24 82 57 43 16 47 94 1 72 17 90 39 30 70 38 16 13 29 93 5 51 66 62 89 31 33 49 39 16 67 15 9 33 72 70 84 70 80 77 75 58 52 91 68 79 24 33 5 55 23 99 32 56 54 16 1 11 100 89 87 44 85 70 85 57 42 14 2 28 80 96 88 58 29 99 21 41 67 31 6 36 66 16 7 45 81 54 56 92 20 62 55 86 68 65 85 53 42 21 21 2 97 64 22 14 38 63 97 97 17 75 75 80 81 72 37 22 88 78 4 70 36 32 9 67 10 9 86 11 97 17 62 56 65 4 39 4 8 62 65 80 40 86 81 43 27 20 87 44 39 93 84 69 94 21 48 89 89 28 11 53 31 80 40 70 36 78 43 70 35 94 15 64 25 24 3 45 27 36 23 77 46 18 1 81 76 70 93 6 2 18 28 65 8 50 68 4 88 87 84 54 55 15 69 15 48 88 30 74 82 19 68 10 76 75 49 66 67 86 29 52 68 50 18 1 59 88 12 39 79 9 56 31 35 74 79 7 68 18 65 50 56 62 74 43 51 28 59 12 91 58 5 81 25 37 36 16 85 49 10 29 91 28 34 4 84 75 51 66 3 100 20 58 89 12 22 61 9 14 11 76 4 5 97 92 63 95 86 89 27 74 22 52 22 3 35 47 78 13 95 67 51 51 87 48 84 74 87 30 79 45 94 44 1 33 3 32 28 51 48 42 91 67 34 30 61 31 54 31 97 41 10 2 33 38 3 1 87 79 5 32 73 40 11 69 16 6 93 3 49 37 15 54 53 83 68 5 11 52 99 24 57 2 57 6 25 62 83 70 76 80 9 30 90 92 74 8 79 81 90 84 77 62 90 41 99 7 100 32 2 45 55 62 78 97 27 5 51 70 83 65 100 21 90 3 84 100 8 7 63 38 15 71 15 74 54 51 75 74 4 78 44 30 20 13 47 50 72 34 26 44 44 68 11 1 36 81 93 5 16 20 75 44 51 8 54 60 34 28 71 85 82 1 70 36 68 9 25 76 36 13 16 76 13 58 32 48 32 75 10 90 78 93 61 60 74 23 36 17 34 84 77 60 97 68 100 99 87 50 72 15 64 11 75 67 50 10 21 12 84 45 15 76 55 44 31 5 24 92 59 80 70 64 17 73 42 95 6 26 40 100 88 28 87 10 8 57 28 70 8 30 35 99 3 27 14 20 71 20 66 8 35 94 3 42 25 31 68 50 44 2 3 56 40 39 74 79 75 93 93 13 22 1 50 61 64 10 39 65 99 5 95 77 38 75 72 27 31 56 23 81 61 83 64 80 2 55 79 98 87 28 12 47 99 79 23 39 64 37 23 59 71 15 35 56 55 50 93 96 41 33 15 88 54 31 24 66 12 81 92 32 78 93 54 12 10 76 13 21 32 62 36 46 81 31 3 18 93 15 95 51 25 69 49 15 43 21 90 8 15 72 29 95 98 89 37 12 97 93 36 79 44 38 97 2 91 56 10 49 49 80 85 2 60 61 24 94 96 63 86 32 27 81 28 49 88 60 24 55 34 26 5 65 64 36 99 3 35 18 33 55 71 54 47 15 57 64 1 2 73 10 13 96 96 48 99 36 4 89 88 9 38 22 95 52 75 26 80 89 79 39 70 18 27 28 78 96 66 23 98 97 49 89 14 58 9 68 74 54 57 32 15 78 25 89 7 54 51 88 91 100 96 25 55 76 72 95 53 80 37 10 1 92 21 69 45 41 91 30 43 41 13 58 67 30 15 61 39 41 78 79 28 76 93 44 11 44 80 58 88 35 95 84 54 76 41 21 42 96 3 81 100 91 90 3 88 66 32 92 81 27 69 59 32 22 52 53 91 53 77 91 16 60 28 93 27 91 45 30 50 49 38 53 92 43 89 82 29 84 99 94 57 46 52 63 86 72 83 99 10 89 80 46 11 57 32 83 58 27 89 83 61 51 31 12 68 21 38 80 54 49 49 72 77 76 10 68 55 32 7 24 44 79 21 12 96 53 39 15 75 55 16 13 41 86 17 36 63 29 45 24 39 62 14 85 55 83 49 57 45 32 76 53 30 3 51 89 32 16 80 16 32 94 88 88 40 6
样例输出
3
3
1
2
4
7
5
5
4
4