MemoryFileTest.java revision 1a44d5dcabc18cd5ef111f732ccff91683a1a093 
1/*
2 * Copyright (C) 2008 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package android.os;
18
19import android.os.MemoryFile;
20import android.test.AndroidTestCase;
21import android.test.suitebuilder.annotation.LargeTest;
22import android.test.suitebuilder.annotation.MediumTest;
23import android.test.suitebuilder.annotation.SmallTest;
24
25import java.io.File;
26import java.io.FileDescriptor;
27import java.io.FileOutputStream;
28import java.io.IOException;
29import java.io.InputStream;
30import java.io.OutputStream;
31import java.util.ArrayList;
32import java.util.List;
33
34public class MemoryFileTest extends AndroidTestCase {
35
36    private void compareBuffers(byte[] buffer1, byte[] buffer2, int length) throws Exception {
37        for (int i = 0; i < length; i++) {
38            if (buffer1[i] != buffer2[i]) {
39                throw new Exception("readBytes did not read back what writeBytes wrote");
40            }
41        }
42    }
43
44    /**
45     * Keep allocating new files till the system purges them.
46     */
47    @MediumTest
48    public void testPurge() throws Exception {
49        List<MemoryFile> files = new ArrayList<MemoryFile>();
50        while (true) {
51            MemoryFile newFile = new MemoryFile("MemoryFileTest", 1000000);
52            newFile.allowPurging(true);
53            newFile.writeBytes(testString, 0, 0, testString.length);
54            files.add(newFile);
55            for (MemoryFile file : files) {
56                try {
57                    file.readBytes(testString, 0, 0, testString.length);
58                } catch (IOException e) {
59                    // Expected
60                    for (MemoryFile fileToClose : files) {
61                        fileToClose.close();
62                    }
63                    return;
64                }
65            }
66        }
67    }
68
69    @SmallTest
70    public void testRun() throws Exception {
71        MemoryFile file = new MemoryFile("MemoryFileTest", 1000000);
72
73        byte[] buffer = new byte[testString.length];
74
75        // check low level accessors
76        file.writeBytes(testString, 0, 2000, testString.length);
77        file.readBytes(buffer, 2000, 0, testString.length);
78        compareBuffers(testString, buffer, testString.length);
79
80        // check streams
81        buffer = new byte[testString.length];
82
83        OutputStream os = file.getOutputStream();
84        os.write(testString);
85
86        InputStream is = file.getInputStream();
87        is.mark(testString.length);
88        is.read(buffer);
89        compareBuffers(testString, buffer, testString.length);
90
91        // test mark/reset
92        buffer = new byte[testString.length];
93        is.reset();
94        is.read(buffer);
95        compareBuffers(testString, buffer, testString.length);
96
97        file.close();
98    }
99
100    // Tests for the IndexOutOfBoundsException cases in read().
101
102    private void readIndexOutOfBoundsException(int offset, int count, String msg)
103            throws Exception {
104        MemoryFile file = new MemoryFile("MemoryFileTest", testString.length);
105        try {
106            file.writeBytes(testString, 0, 0, testString.length);
107            InputStream is = file.getInputStream();
108            byte[] buffer = new byte[testString.length + 10];
109            try {
110                is.read(buffer, offset, count);
111                fail(msg);
112            } catch (IndexOutOfBoundsException ex) {
113                // this is what should happen
114            } finally {
115                is.close();
116            }
117        } finally {
118            file.close();
119        }
120    }
121
122    @SmallTest
123    public void testReadNegativeOffset() throws Exception {
124        readIndexOutOfBoundsException(-1, 5,
125                "read() with negative offset should throw IndexOutOfBoundsException");
126    }
127
128    @SmallTest
129    public void testReadNegativeCount() throws Exception {
130        readIndexOutOfBoundsException(5, -1,
131                "read() with negative length should throw IndexOutOfBoundsException");
132    }
133
134    @SmallTest
135    public void testReadOffsetOverflow() throws Exception {
136        readIndexOutOfBoundsException(testString.length + 10, 5,
137                "read() with offset outside buffer should throw IndexOutOfBoundsException");
138    }
139
140    @SmallTest
141    public void testReadOffsetCountOverflow() throws Exception {
142        readIndexOutOfBoundsException(testString.length, 11,
143                "read() with offset + count outside buffer should throw IndexOutOfBoundsException");
144    }
145
146    // Test behavior of read() at end of file
147    @SmallTest
148    public void testReadEOF() throws Exception {
149        MemoryFile file = new MemoryFile("MemoryFileTest", testString.length);
150        try {
151            file.writeBytes(testString, 0, 0, testString.length);
152            InputStream is = file.getInputStream();
153            try {
154                byte[] buffer = new byte[testString.length + 10];
155                // read() with count larger than data should succeed, and return # of bytes read
156                assertEquals(testString.length, is.read(buffer));
157                compareBuffers(testString, buffer, testString.length);
158                // Read at EOF should return -1
159                assertEquals(-1, is.read());
160            } finally {
161                is.close();
162            }
163        } finally {
164            file.close();
165        }
166    }
167
168    // Tests that close() is idempotent
169    @SmallTest
170    public void testCloseClose() throws Exception {
171        MemoryFile file = new MemoryFile("MemoryFileTest", 1000000);
172        byte[] data = new byte[512];
173        file.writeBytes(data, 0, 0, 128);
174        file.close();
175        file.close();
176    }
177
178    // Tests that we can't read from a closed memory file
179    @SmallTest
180    public void testCloseRead() throws Exception {
181        MemoryFile file = new MemoryFile("MemoryFileTest", 1000000);
182        file.close();
183
184        try {
185            byte[] data = new byte[512];
186            assertEquals(128, file.readBytes(data, 0, 0, 128));
187            fail("readBytes() after close() did not throw IOException.");
188        } catch (IOException e) {
189            // this is what should happen
190        }
191    }
192
193    // Tests that we can't write to a closed memory file
194    @SmallTest
195    public void testCloseWrite() throws Exception {
196        MemoryFile file = new MemoryFile("MemoryFileTest", 1000000);
197        file.close();
198
199        try {
200            byte[] data = new byte[512];
201            file.writeBytes(data, 0, 0, 128);
202            fail("writeBytes() after close() did not throw IOException.");
203        } catch (IOException e) {
204            // this is what should happen
205        }
206    }
207
208    // Tests that we can't call allowPurging() after close()
209    @SmallTest
210    public void testCloseAllowPurging() throws Exception {
211        MemoryFile file = new MemoryFile("MemoryFileTest", 1000000);
212        byte[] data = new byte[512];
213        file.writeBytes(data, 0, 0, 128);
214        file.close();
215
216        try {
217            file.allowPurging(true);
218            fail("allowPurging() after close() did not throw IOException.");
219        } catch (IOException e) {
220            // this is what should happen
221        }
222    }
223
224    // Tests that we don't leak file descriptors or mmap areas
225    @LargeTest
226    public void testCloseLeak() throws Exception {
227        // open enough memory files that we should run out of
228        // file descriptors or address space if we leak either.
229        for (int i = 0; i < 1025; i++) {
230            MemoryFile file = new MemoryFile("MemoryFileTest", 5000000);
231            file.writeBytes(testString, 0, 0, testString.length);
232            file.close();
233        }
234    }
235
236    @SmallTest
237    public void testIsMemoryFile() throws Exception {
238        MemoryFile file = new MemoryFile("MemoryFileTest", 1000000);
239        FileDescriptor fd = file.getFileDescriptor();
240        assertNotNull(fd);
241        assertTrue(fd.valid());
242        assertTrue(MemoryFile.isMemoryFile(fd));
243        file.close();
244
245        assertFalse(MemoryFile.isMemoryFile(FileDescriptor.in));
246        assertFalse(MemoryFile.isMemoryFile(FileDescriptor.out));
247        assertFalse(MemoryFile.isMemoryFile(FileDescriptor.err));
248
249        File tempFile = File.createTempFile("MemoryFileTest",".tmp", getContext().getFilesDir());
250        assertNotNull(file);
251        FileOutputStream out = null;
252        try {
253            out = new FileOutputStream(tempFile);
254            FileDescriptor fileFd = out.getFD();
255            assertNotNull(fileFd);
256            assertFalse(MemoryFile.isMemoryFile(fileFd));
257        } finally {
258            if (out != null) {
259                out.close();
260            }
261            tempFile.delete();
262        }
263    }
264
265    @SmallTest
266    public void testFileDescriptor() throws Exception {
267        MemoryFile file = new MemoryFile("MemoryFileTest", 1000000);
268        MemoryFile ref = new MemoryFile(file.getFileDescriptor(), file.length(), "r");
269        byte[] buffer;
270
271        // write to original, read from reference
272        file.writeBytes(testString, 0, 2000, testString.length);
273        buffer = new byte[testString.length];
274        ref.readBytes(buffer, 2000, 0, testString.length);
275        compareBuffers(testString, buffer, testString.length);
276
277        file.close();
278        ref.close();  // Doesn't actually do anything, since the file descriptor is not dup(2):ed
279    }
280
281    private static final byte[] testString = new byte[] {
282        3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4, 3, 3, 8, 3, 2, 7, 9, 5, 0, 2, 8, 8, 4, 1, 9, 7, 1, 6, 9, 3, 9, 9, 3, 7, 5, 1, 0, 5, 8, 2, 0, 9, 7, 4, 9, 4, 4, 5, 9, 2, 3, 0, 7, 8, 1, 6, 4,
283        0, 6, 2, 8, 6, 2, 0, 8, 9, 9, 8, 6, 2, 8, 0, 3, 4, 8, 2, 5, 3, 4, 2, 1, 1, 7, 0, 6, 7, 9, 8, 2, 1, 4, 8, 0, 8, 6, 5, 1, 3, 2, 8, 2, 3, 0, 6, 6, 4, 7, 0, 9, 3, 8, 4, 4, 6, 0, 9, 5, 5, 0, 5, 8, 2, 2, 3, 1, 7, 2,
284        5, 3, 5, 9, 4, 0, 8, 1, 2, 8, 4, 8, 1, 1, 1, 7, 4, 5, 0, 2, 8, 4, 1, 0, 2, 7, 0, 1, 9, 3, 8, 5, 2, 1, 1, 0, 5, 5, 5, 9, 6, 4, 4, 6, 2, 2, 9, 4, 8, 9, 5, 4, 9, 3, 0, 3, 8, 1, 9, 6, 4, 4, 2, 8, 8, 1, 0, 9, 7, 5,
285        6, 6, 5, 9, 3, 3, 4, 4, 6, 1, 2, 8, 4, 7, 5, 6, 4, 8, 2, 3, 3, 7, 8, 6, 7, 8, 3, 1, 6, 5, 2, 7, 1, 2, 0, 1, 9, 0, 9, 1, 4, 5, 6, 4, 8, 5, 6, 6, 9, 2, 3, 4, 6, 0, 3, 4, 8, 6, 1, 0, 4, 5, 4, 3, 2, 6, 6, 4, 8, 2,
286        1, 3, 3, 9, 3, 6, 0, 7, 2, 6, 0, 2, 4, 9, 1, 4, 1, 2, 7, 3, 7, 2, 4, 5, 8, 7, 0, 0, 6, 6, 0, 6, 3, 1, 5, 5, 8, 8, 1, 7, 4, 8, 8, 1, 5, 2, 0, 9, 2, 0, 9, 6, 2, 8, 2, 9, 2, 5, 4, 0, 9, 1, 7, 1, 5, 3, 6, 4, 3, 6,
287        7, 8, 9, 2, 5, 9, 0, 3, 6, 0, 0, 1, 1, 3, 3, 0, 5, 3, 0, 5, 4, 8, 8, 2, 0, 4, 6, 6, 5, 2, 1, 3, 8, 4, 1, 4, 6, 9, 5, 1, 9, 4, 1, 5, 1, 1, 6, 0, 9, 4, 3, 3, 0, 5, 7, 2, 7, 0, 3, 6, 5, 7, 5, 9, 5, 9, 1, 9, 5, 3,
288        0, 9, 2, 1, 8, 6, 1, 1, 7, 3, 8, 1, 9, 3, 2, 6, 1, 1, 7, 9, 3, 1, 0, 5, 1, 1, 8, 5, 4, 8, 0, 7, 4, 4, 6, 2, 3, 7, 9, 9, 6, 2, 7, 4, 9, 5, 6, 7, 3, 5, 1, 8, 8, 5, 7, 5, 2, 7, 2, 4, 8, 9, 1, 2, 2, 7, 9, 3, 8, 1,
289        8, 3, 0, 1, 1, 9, 4, 9, 1, 2, 9, 8, 3, 3, 6, 7, 3, 3, 6, 2, 4, 4, 0, 6, 5, 6, 6, 4, 3, 0, 8, 6, 0, 2, 1, 3, 9, 4, 9, 4, 6, 3, 9, 5, 2, 2, 4, 7, 3, 7, 1, 9, 0, 7, 0, 2, 1, 7, 9, 8, 6, 0, 9, 4, 3, 7, 0, 2, 7, 7,
290        0, 5, 3, 9, 2, 1, 7, 1, 7, 6, 2, 9, 3, 1, 7, 6, 7, 5, 2, 3, 8, 4, 6, 7, 4, 8, 1, 8, 4, 6, 7, 6, 6, 9, 4, 0, 5, 1, 3, 2, 0, 0, 0, 5, 6, 8, 1, 2, 7, 1, 4, 5, 2, 6, 3, 5, 6, 0, 8, 2, 7, 7, 8, 5, 7, 7, 1, 3, 4, 2,
291        7, 5, 7, 7, 8, 9, 6, 0, 9, 1, 7, 3, 6, 3, 7, 1, 7, 8, 7, 2, 1, 4, 6, 8, 4, 4, 0, 9, 0, 1, 2, 2, 4, 9, 5, 3, 4, 3, 0, 1, 4, 6, 5, 4, 9, 5, 8, 5, 3, 7, 1, 0, 5, 0, 7, 9, 2, 2, 7, 9, 6, 8, 9, 2, 5, 8, 9, 2, 3, 5,
292        4, 2, 0, 1, 9, 9, 5, 6, 1, 1, 2, 1, 2, 9, 0, 2, 1, 9, 6, 0, 8, 6, 4, 0, 3, 4, 4, 1, 8, 1, 5, 9, 8, 1, 3, 6, 2, 9, 7, 7, 4, 7, 7, 1, 3, 0, 9, 9, 6, 0, 5, 1, 8, 7, 0, 7, 2, 1, 1, 3, 4, 9, 9, 9, 9, 9, 9, 8, 3, 7,
293        2, 9, 7, 8, 0, 4, 9, 9, 5, 1, 0, 5, 9, 7, 3, 1, 7, 3, 2, 8, 1, 6, 0, 9, 6, 3, 1, 8, 5, 9, 5, 0, 2, 4, 4, 5, 9, 4, 5, 5, 3, 4, 6, 9, 0, 8, 3, 0, 2, 6, 4, 2, 5, 2, 2, 3, 0, 8, 2, 5, 3, 3, 4, 4, 6, 8, 5, 0, 3, 5,
294        2, 6, 1, 9, 3, 1, 1, 8, 8, 1, 7, 1, 0, 1, 0, 0, 0, 3, 1, 3, 7, 8, 3, 8, 7, 5, 2, 8, 8, 6, 5, 8, 7, 5, 3, 3, 2, 0, 8, 3, 8, 1, 4, 2, 0, 6, 1, 7, 1, 7, 7, 6, 6, 9, 1, 4, 7, 3, 0, 3, 5, 9, 8, 2, 5, 3, 4, 9, 0, 4,
295        2, 8, 7, 5, 5, 4, 6, 8, 7, 3, 1, 1, 5, 9, 5, 6, 2, 8, 6, 3, 8, 8, 2, 3, 5, 3, 7, 8, 7, 5, 9, 3, 7, 5, 1, 9, 5, 7, 7, 8, 1, 8, 5, 7, 7, 8, 0, 5, 3, 2, 1, 7, 1, 2, 2, 6, 8, 0, 6, 6, 1, 3, 0, 0, 1, 9, 2, 7, 8, 7,
296        6, 6, 1, 1, 1, 9, 5, 9, 0, 9, 2, 1, 6, 4, 2, 0, 1, 9, 8, 9, 3, 8, 0, 9, 5, 2, 5, 7, 2, 0, 1, 0, 6, 5, 4, 8, 5, 8, 6, 3, 2, 7, 8, 8, 6, 5, 9, 3, 6, 1, 5, 3, 3, 8, 1, 8, 2, 7, 9, 6, 8, 2, 3, 0, 3, 0, 1, 9, 5, 2,
297        0, 3, 5, 3, 0, 1, 8, 5, 2, 9, 6, 8, 9, 9, 5, 7, 7, 3, 6, 2, 2, 5, 9, 9, 4, 1, 3, 8, 9, 1, 2, 4, 9, 7, 2, 1, 7, 7, 5, 2, 8, 3, 4, 7, 9, 1, 3, 1, 5, 1, 5, 5, 7, 4, 8, 5, 7, 2, 4, 2, 4, 5, 4, 1, 5, 0, 6, 9, 5, 9,
298        5, 0, 8, 2, 9, 5, 3, 3, 1, 1, 6, 8, 6, 1, 7, 2, 7, 8, 5, 5, 8, 8, 9, 0, 7, 5, 0, 9, 8, 3, 8, 1, 7, 5, 4, 6, 3, 7, 4, 6, 4, 9, 3, 9, 3, 1, 9, 2, 5, 5, 0, 6, 0, 4, 0, 0, 9, 2, 7, 7, 0, 1, 6, 7, 1, 1, 3, 9, 0, 0,
299        9, 8, 4, 8, 8, 2, 4, 0, 1, 2, 8, 5, 8, 3, 6, 1, 6, 0, 3, 5, 6, 3, 7, 0, 7, 6, 6, 0, 1, 0, 4, 7, 1, 0, 1, 8, 1, 9, 4, 2, 9, 5, 5, 5, 9, 6, 1, 9, 8, 9, 4, 6, 7, 6, 7, 8, 3, 7, 4, 4, 9, 4, 4, 8, 2, 5, 5, 3, 7, 9,
300        7, 7, 4, 7, 2, 6, 8, 4, 7, 1, 0, 4, 0, 4, 7, 5, 3, 4, 6, 4, 6, 2, 0, 8, 0, 4, 6, 6, 8, 4, 2, 5, 9, 0, 6, 9, 4, 9, 1, 2, 9, 3, 3, 1, 3, 6, 7, 7, 0, 2, 8, 9, 8, 9, 1, 5, 2, 1, 0, 4, 7, 5, 2, 1, 6, 2, 0, 5, 6, 9,
301        6, 6, 0, 2, 4, 0, 5, 8, 0, 3, 8, 1, 5, 0, 1, 9, 3, 5, 1, 1, 2, 5, 3, 3, 8, 2, 4, 3, 0, 0, 3, 5, 5, 8, 7, 6, 4, 0, 2, 4, 7, 4, 9, 6, 4, 7, 3, 2, 6, 3, 9, 1, 4, 1, 9, 9, 2, 7, 2, 6, 0, 4, 2, 6, 9, 9, 2, 2, 7, 9,
302        6, 7, 8, 2, 3, 5, 4, 7, 8, 1, 6, 3, 6, 0, 0, 9, 3, 4, 1, 7, 2, 1, 6, 4, 1, 2, 1, 9, 9, 2, 4, 5, 8, 6, 3, 1, 5, 0, 3, 0, 2, 8, 6, 1, 8, 2, 9, 7, 4, 5, 5, 5, 7, 0, 6, 7, 4, 9, 8, 3, 8, 5, 0, 5, 4, 9, 4, 5, 8, 8,
303        5, 8, 6, 9, 2, 6, 9, 9, 5, 6, 9, 0, 9, 2, 7, 2, 1, 0, 7, 9, 7, 5, 0, 9, 3, 0, 2, 9, 5, 5, 3, 2, 1, 1, 6, 5, 3, 4, 4, 9, 8, 7, 2, 0, 2, 7, 5, 5, 9, 6, 0, 2, 3, 6, 4, 8, 0, 6, 6, 5, 4, 9, 9, 1, 1, 9, 8, 8, 1, 8,
304        3, 4, 7, 9, 7, 7, 5, 3, 5, 6, 6, 3, 6, 9, 8, 0, 7, 4, 2, 6, 5, 4, 2, 5, 2, 7, 8, 6, 2, 5, 5, 1, 8, 1, 8, 4, 1, 7, 5, 7, 4, 6, 7, 2, 8, 9, 0, 9, 7, 7, 7, 7, 2, 7, 9, 3, 8, 0, 0, 0, 8, 1, 6, 4, 7, 0, 6, 0, 0, 1,
305        6, 1, 4, 5, 2, 4, 9, 1, 9, 2, 1, 7, 3, 2, 1, 7, 2, 1, 4, 7, 7, 2, 3, 5, 0, 1, 4, 1, 4, 4, 1, 9, 7, 3, 5, 6, 8, 5, 4, 8, 1, 6, 1, 3, 6, 1, 1, 5, 7, 3, 5, 2, 5, 5, 2, 1, 3, 3, 4, 7, 5, 7, 4, 1, 8, 4, 9, 4, 6, 8,
306        4, 3, 8, 5, 2, 3, 3, 2, 3, 9, 0, 7, 3, 9, 4, 1, 4, 3, 3, 3, 4, 5, 4, 7, 7, 6, 2, 4, 1, 6, 8, 6, 2, 5, 1, 8, 9, 8, 3, 5, 6, 9, 4, 8, 5, 5, 6, 2, 0, 9, 9, 2, 1, 9, 2, 2, 2, 1, 8, 4, 2, 7, 2, 5, 5, 0, 2, 5, 4, 2,
307        5, 6, 8, 8, 7, 6, 7, 1, 7, 9, 0, 4, 9, 4, 6, 0, 1, 6, 5, 3, 4, 6, 6, 8, 0, 4, 9, 8, 8, 6, 2, 7, 2, 3, 2, 7, 9, 1, 7, 8, 6, 0, 8, 5, 7, 8, 4, 3, 8, 3, 8, 2, 7, 9, 6, 7, 9, 7, 6, 6, 8, 1, 4, 5, 4, 1, 0, 0, 9, 5,
308        3, 8, 8, 3, 7, 8, 6, 3, 6, 0, 9, 5, 0, 6, 8, 0, 0, 6, 4, 2, 2, 5, 1, 2, 5, 2, 0, 5, 1, 1, 7, 3, 9, 2, 9, 8, 4, 8, 9, 6, 0, 8, 4, 1, 2, 8, 4, 8, 8, 6, 2, 6, 9, 4, 5, 6, 0, 4, 2, 4, 1, 9, 6, 5, 2, 8, 5, 0, 2, 2,
309        2, 1, 0, 6, 6, 1, 1, 8, 6, 3, 0, 6, 7, 4, 4, 2, 7, 8, 6, 2, 2, 0, 3, 9, 1, 9, 4, 9, 4, 5, 0, 4, 7, 1, 2, 3, 7, 1, 3, 7, 8, 6, 9, 6, 0, 9, 5, 6, 3, 6, 4, 3, 7, 1, 9, 1, 7, 2, 8, 7, 4, 6, 7, 7, 6, 4, 6, 5, 7, 5,
310        7, 3, 9, 6, 2, 4, 1, 3, 8, 9, 0, 8, 6, 5, 8, 3, 2, 6, 4, 5, 9, 9, 5, 8, 1, 3, 3, 9, 0, 4, 7, 8, 0, 2, 7, 5, 9, 0, 0, 9, 9, 4, 6, 5, 7, 6, 4, 0, 7, 8, 9, 5, 1, 2, 6, 9, 4, 6, 8, 3, 9, 8, 3, 5, 2, 5, 9, 5, 7, 0,
311        9, 8, 2, 5, 8, 2, 2, 6, 2, 0, 5, 2, 2, 4, 8, 9, 4, 0, 7, 7, 2, 6, 7, 1, 9, 4, 7, 8, 2, 6, 8, 4, 8, 2, 6, 0, 1, 4, 7, 6, 9, 9, 0, 9, 0, 2, 6, 4, 0, 1, 3, 6, 3, 9, 4, 4, 3, 7, 4, 5, 5, 3, 0, 5, 0, 6, 8, 2, 0, 3,
312        4, 9, 6, 2, 5, 2, 4, 5, 1, 7, 4, 9, 3, 9, 9, 6, 5, 1, 4, 3, 1, 4, 2, 9, 8, 0, 9, 1, 9, 0, 6, 5, 9, 2, 5, 0, 9, 3, 7, 2, 2, 1, 6, 9, 6, 4, 6, 1, 5, 1, 5, 7, 0, 9, 8, 5, 8, 3, 8, 7, 4, 1, 0, 5, 9, 7, 8, 8, 5, 9,
313        5, 9, 7, 7, 2, 9, 7, 5, 4, 9, 8, 9, 3, 0, 1, 6, 1, 7, 5, 3, 9, 2, 8, 4, 6, 8, 1, 3, 8, 2, 6, 8, 6, 8, 3, 8, 6, 8, 9, 4, 2, 7, 7, 4, 1, 5, 5, 9, 9, 1, 8, 5, 5, 9, 2, 5, 2, 4, 5, 9, 5, 3, 9, 5, 9, 4, 3, 1, 0, 4,
314        9, 9, 7, 2, 5, 2, 4, 6, 8, 0, 8, 4, 5, 9, 8, 7, 2, 7, 3, 6, 4, 4, 6, 9, 5, 8, 4, 8, 6, 5, 3, 8, 3, 6, 7, 3, 6, 2, 2, 2, 6, 2, 6, 0, 9, 9, 1, 2, 4, 6, 0, 8, 0, 5, 1, 2, 4, 3, 8, 8, 4, 3, 9, 0, 4, 5, 1, 2, 4, 4,
315        1, 3, 6, 5, 4, 9, 7, 6, 2, 7, 8, 0, 7, 9, 7, 7, 1, 5, 6, 9, 1, 4, 3, 5, 9, 9, 7, 7, 0, 0, 1, 2, 9, 6, 1, 6, 0, 8, 9, 4, 4, 1, 6, 9, 4, 8, 6, 8, 5, 5, 5, 8, 4, 8, 4, 0, 6, 3, 5, 3, 4, 2, 2, 0, 7, 2, 2, 2, 5, 8,
316        2, 8, 4, 8, 8, 6, 4, 8, 1, 5, 8, 4, 5, 6, 0, 2, 8, 5, 0, 6, 0, 1, 6, 8, 4, 2, 7, 3, 9, 4, 5, 2, 2, 6, 7, 4, 6, 7, 6, 7, 8, 8, 9, 5, 2, 5, 2, 1, 3, 8, 5, 2, 2, 5, 4, 9, 9, 5, 4, 6, 6, 6, 7, 2, 7, 8, 2, 3, 9, 8,
317        6, 4, 5, 6, 5, 9, 6, 1, 1, 6, 3, 5, 4, 8, 8, 6, 2, 3, 0, 5, 7, 7, 4, 5, 6, 4, 9, 8, 0, 3, 5, 5, 9, 3, 6, 3, 4, 5, 6, 8, 1, 7, 4, 3, 2, 4, 1, 1, 2, 5, 1, 5, 0, 7, 6, 0, 6, 9, 4, 7, 9, 4, 5, 1, 0, 9, 6, 5, 9, 6,
318        0, 9, 4, 0, 2, 5, 2, 2, 8, 8, 7, 9, 7, 1, 0, 8, 9, 3, 1, 4, 5, 6, 6, 9, 1, 3, 6, 8, 6, 7, 2, 2, 8, 7, 4, 8, 9, 4, 0, 5, 6, 0, 1, 0, 1, 5, 0, 3, 3, 0, 8, 6, 1, 7, 9, 2, 8, 6, 8, 0, 9, 2, 0, 8, 7, 4, 7, 6, 0, 9,
319        1, 7, 8, 2, 4, 9, 3, 8, 5, 8, 9, 0, 0, 9, 7, 1, 4, 9, 0, 9, 6, 7, 5, 9, 8, 5, 2, 6, 1, 3, 6, 5, 5, 4, 9, 7, 8, 1, 8, 9, 3, 1, 2, 9, 7, 8, 4, 8, 2, 1, 6, 8, 2, 9, 9, 8, 9, 4, 8, 7, 2, 2, 6, 5, 8, 8, 0, 4, 8, 5,
320        7, 5, 6, 4, 0, 1, 4, 2, 7, 0, 4, 7, 7, 5, 5, 5, 1, 3, 2, 3, 7, 9, 6, 4, 1, 4, 5, 1, 5, 2, 3, 7, 4, 6, 2, 3, 4, 3, 6, 4, 5, 4, 2, 8, 5, 8, 4, 4, 4, 7, 9, 5, 2, 6, 5, 8, 6, 7, 8, 2, 1, 0, 5, 1, 1, 4, 1, 3, 5, 4,
321        7, 3, 5, 7, 3, 9, 5, 2, 3, 1, 1, 3, 4, 2, 7, 1, 6, 6, 1, 0, 2, 1, 3, 5, 9, 6, 9, 5, 3, 6, 2, 3, 1, 4, 4, 2, 9, 5, 2, 4, 8, 4, 9, 3, 7, 1, 8, 7, 1, 1, 0, 1, 4, 5, 7, 6, 5, 4, 0, 3, 5, 9, 0, 2, 7, 9, 9, 3, 4, 4,
322        0, 3, 7, 4, 2, 0, 0, 7, 3, 1, 0, 5, 7, 8, 5, 3, 9, 0, 6, 2, 1, 9, 8, 3, 8, 7, 4, 4, 7, 8, 0, 8, 4, 7, 8, 4, 8, 9, 6, 8, 3, 3, 2, 1, 4, 4, 5, 7, 1, 3, 8, 6, 8, 7, 5, 1, 9, 4, 3, 5, 0, 6, 4, 3, 0, 2, 1, 8, 4, 5,
323        3, 1, 9, 1, 0, 4, 8, 4, 8, 1, 0, 0, 5, 3, 7, 0, 6, 1, 4, 6, 8, 0, 6, 7, 4, 9, 1, 9, 2, 7, 8, 1, 9, 1, 1, 9, 7, 9, 3, 9, 9, 5, 2, 0, 6, 1, 4, 1, 9, 6, 6, 3, 4, 2, 8, 7, 5, 4, 4, 4, 0, 6, 4, 3, 7, 4, 5, 1, 2, 3,
324        7, 1, 8, 1, 9, 2, 1, 7, 9, 9, 9, 8, 3, 9, 1, 0, 1, 5, 9, 1, 9, 5, 6, 1, 8, 1, 4, 6, 7, 5, 1, 4, 2, 6, 9, 1, 2, 3, 9, 7, 4, 8, 9, 4, 0, 9, 0, 7, 1, 8, 6, 4, 9, 4, 2, 3, 1, 9, 6, 1, 5, 6, 7, 9, 4, 5, 2, 0, 8, 0,
325        9, 5, 1, 4, 6, 5, 5, 0, 2, 2, 5, 2, 3, 1, 6, 0, 3, 8, 8, 1, 9, 3, 0, 1, 4, 2, 0, 9, 3, 7, 6, 2, 1, 3, 7, 8, 5, 5, 9, 5, 6, 6, 3, 8, 9, 3, 7, 7, 8, 7, 0, 8, 3, 0, 3, 9, 0, 6, 9, 7, 9, 2, 0, 7, 7, 3, 4, 6, 7, 2,
326        2, 1, 8, 2, 5, 6, 2, 5, 9, 9, 6, 6, 1, 5, 0, 1, 4, 2, 1, 5, 0, 3, 0, 6, 8, 0, 3, 8, 4, 4, 7, 7, 3, 4, 5, 4, 9, 2, 0, 2, 6, 0, 5, 4, 1, 4, 6, 6, 5, 9, 2, 5, 2, 0, 1, 4, 9, 7, 4, 4, 2, 8, 5, 0, 7, 3, 2, 5, 1, 8,
327        6, 6, 6, 0, 0, 2, 1, 3, 2, 4, 3, 4, 0, 8, 8, 1, 9, 0, 7, 1, 0, 4, 8, 6, 3, 3, 1, 7, 3, 4, 6, 4, 9, 6, 5, 1, 4, 5, 3, 9, 0, 5, 7, 9, 6, 2, 6, 8, 5, 6, 1, 0, 0, 5, 5, 0, 8, 1, 0, 6, 6, 5, 8, 7, 9, 6, 9, 9, 8, 1,
328        6, 3, 5, 7, 4, 7, 3, 6, 3, 8, 4, 0, 5, 2, 5, 7, 1, 4, 5, 9, 1, 0, 2, 8, 9, 7, 0, 6, 4, 1, 4, 0, 1, 1, 0, 9, 7, 1, 2, 0, 6, 2, 8, 0, 4, 3, 9, 0, 3, 9, 7, 5, 9, 5, 1, 5, 6, 7, 7, 1, 5, 7, 7, 0, 0, 4, 2, 0, 3, 3,
329        7, 8, 6, 9, 9, 3, 6, 0, 0, 7, 2, 3, 0, 5, 5, 8, 7, 6, 3, 1, 7, 6, 3, 5, 9, 4, 2, 1, 8, 7, 3, 1, 2, 5, 1, 4, 7, 1, 2, 0, 5, 3, 2, 9, 2, 8, 1, 9, 1, 8, 2, 6, 1, 8, 6, 1, 2, 5, 8, 6, 7, 3, 2, 1, 5, 7, 9, 1, 9, 8,
330        4, 1, 4, 8, 4, 8, 8, 2, 9, 1, 6, 4, 4, 7, 0, 6, 0, 9, 5, 7, 5, 2, 7, 0, 6, 9, 5, 7, 2, 2, 0, 9, 1, 7, 5, 6, 7, 1, 1, 6, 7, 2, 2, 9, 1, 0, 9, 8, 1, 6, 9, 0, 9, 1, 5, 2, 8, 0, 1, 7, 3, 5, 0, 6, 7, 1, 2, 7, 4, 8,
331        5, 8, 3, 2, 2, 2, 8, 7, 1, 8, 3, 5, 2, 0, 9, 3, 5, 3, 9, 6, 5, 7, 2, 5, 1, 2, 1, 0, 8, 3, 5, 7, 9, 1, 5, 1, 3, 6, 9, 8, 8, 2, 0, 9, 1, 4, 4, 4, 2, 1, 0, 0, 6, 7, 5, 1, 0, 3, 3, 4, 6, 7, 1, 1, 0, 3, 1, 4, 1, 2,
332        6, 7, 1, 1, 1, 3, 6, 9, 9, 0, 8, 6, 5, 8, 5, 1, 6, 3, 9, 8, 3, 1, 5, 0, 1, 9, 7, 0, 1, 6, 5, 1, 5, 1, 1, 6, 8, 5, 1, 7, 1, 4, 3, 7, 6, 5, 7, 6, 1, 8, 3, 5, 1, 5, 5, 6, 5, 0, 8, 8, 4, 9, 0, 9, 9, 8, 9, 8, 5, 9,
333        9, 8, 2, 3, 8, 7, 3, 4, 5, 5, 2, 8, 3, 3, 1, 6, 3, 5, 5, 0, 7, 6, 4, 7, 9, 1, 8, 5, 3, 5, 8, 9, 3, 2, 2, 6, 1, 8, 5, 4, 8, 9, 6, 3, 2, 1, 3, 2, 9, 3, 3, 0, 8, 9, 8, 5, 7, 0, 6, 4, 2, 0, 4, 6, 7, 5, 2, 5, 9, 0,
334        7, 0, 9, 1, 5, 4, 8, 1, 4, 1, 6, 5, 4, 9, 8, 5, 9, 4, 6, 1, 6, 3, 7, 1, 8, 0, 2, 7, 0, 9, 8, 1, 9, 9, 4, 3, 0, 9, 9, 2, 4, 4, 8, 8, 9, 5, 7, 5, 7, 1, 2, 8, 2, 8, 9, 0, 5, 9, 2, 3, 2, 3, 3, 2, 6, 0, 9, 7, 2, 9,
335        9, 7, 1, 2, 0, 8, 4, 4, 3, 3, 5, 7, 3, 2, 6, 5, 4, 8, 9, 3, 8, 2, 3, 9, 1, 1, 9, 3, 2, 5, 9, 7, 4, 6, 3, 6, 6, 7, 3, 0, 5, 8, 3, 6, 0, 4, 1, 4, 2, 8, 1, 3, 8, 8, 3, 0, 3, 2, 0, 3, 8, 2, 4, 9, 0, 3, 7, 5, 8, 9,
336        8, 5, 2, 4, 3, 7, 4, 4, 1, 7, 0, 2, 9, 1, 3, 2, 7, 6, 5, 6, 1, 8, 0, 9, 3, 7, 7, 3, 4, 4, 4, 0, 3, 0, 7, 0, 7, 4, 6, 9, 2, 1, 1, 2, 0, 1, 9, 1, 3, 0, 2, 0, 3, 3, 0, 3, 8, 0, 1, 9, 7, 6, 2, 1, 1, 0, 1, 1, 0, 0,
337        4, 4, 9, 2, 9, 3, 2, 1, 5, 1, 6, 0, 8, 4, 2, 4, 4, 4, 8, 5, 9, 6, 3, 7, 6, 6, 9, 8, 3, 8, 9, 5, 2, 2, 8, 6, 8, 4, 7, 8, 3, 1, 2, 3, 5, 5, 2, 6, 5, 8, 2, 1, 3, 1, 4, 4, 9, 5, 7, 6, 8, 5, 7, 2, 6, 2, 4, 3, 3, 4,
338        4, 1, 8, 9, 3, 0, 3, 9, 6, 8, 6, 4, 2, 6, 2, 4, 3, 4, 1, 0, 7, 7, 3, 2, 2, 6, 9, 7, 8, 0, 2, 8, 0, 7, 3, 1, 8, 9, 1, 5, 4, 4, 1, 1, 0, 1, 0, 4, 4, 6, 8, 2, 3, 2, 5, 2, 7, 1, 6, 2, 0, 1, 0, 5, 2, 6, 5, 2, 2, 7,
339        2, 1, 1, 1, 6, 6, 0, 3, 9, 6, 6, 6, 5, 5, 7, 3, 0, 9, 2, 5, 4, 7, 1, 1, 0, 5, 5, 7, 8, 5, 3, 7, 6, 3, 4, 6, 6, 8, 2, 0, 6, 5, 3, 1, 0, 9, 8, 9, 6, 5, 2, 6, 9, 1, 8, 6, 2, 0, 5, 6, 4, 7, 6, 9, 3, 1, 2, 5, 7, 0,
340        5, 8, 6, 3, 5, 6, 6, 2, 0, 1, 8, 5, 5, 8, 1, 0, 0, 7, 2, 9, 3, 6, 0, 6, 5, 9, 8, 7, 6, 4, 8, 6, 1, 1, 7, 9, 1, 0, 4, 5, 3, 3, 4, 8, 8, 5, 0, 3, 4, 6, 1, 1, 3, 6, 5, 7, 6, 8, 6, 7, 5, 3, 2, 4, 9, 4, 4, 1, 6, 6,
341        8, 0, 3, 9, 6, 2, 6, 5, 7, 9, 7, 8, 7, 7, 1, 8, 5, 5, 6, 0, 8, 4, 5, 5, 2, 9, 6, 5, 4, 1, 2, 6, 6, 5, 4, 0, 8, 5, 3, 0, 6, 1, 4, 3, 4, 4, 4, 3, 1, 8, 5, 8, 6, 7, 6, 9, 7, 5, 1, 4, 5, 6, 6, 1, 4, 0, 6, 8, 0, 0,
342        7, 0, 0, 2, 3, 7, 8, 7, 7, 6, 5, 9, 1, 3, 4, 4, 0, 1, 7, 1, 2, 7, 4, 9, 4, 7, 0, 4, 2, 0, 5, 6, 2, 2, 3, 0, 5, 3, 8, 9, 9, 4, 5, 6, 1, 3, 1, 4, 0, 7, 1, 1, 2, 7, 0, 0, 0, 4, 0, 7, 8, 5, 4, 7, 3, 3, 2, 6, 9, 9,
343        3, 9, 0, 8, 1, 4, 5, 4, 6, 6, 4, 6, 4, 5, 8, 8, 0, 7, 9, 7, 2, 7, 0, 8, 2, 6, 6, 8, 3, 0, 6, 3, 4, 3, 2, 8, 5, 8, 7, 8, 5, 6, 9, 8, 3, 0, 5, 2, 3, 5, 8, 0, 8, 9, 3, 3, 0, 6, 5, 7, 5, 7, 4, 0, 6, 7, 9, 5, 4, 5,
344        7, 1, 6, 3, 7, 7, 5, 2, 5, 4, 2, 0, 2, 1, 1, 4, 9, 5, 5, 7, 6, 1, 5, 8, 1, 4, 0, 0, 2, 5, 0, 1, 2, 6, 2, 2, 8, 5, 9, 4, 1, 3, 0, 2, 1, 6, 4, 7, 1, 5, 5, 0, 9, 7, 9, 2, 5, 9, 2, 3, 0, 9, 9, 0, 7, 9, 6, 5, 4, 7,
345        3, 7, 6, 1, 2, 5, 5, 1, 7, 6, 5, 6, 7, 5, 1, 3, 5, 7, 5, 1, 7, 8, 2, 9, 6, 6, 6, 4, 5, 4, 7, 7, 9, 1, 7, 4, 5, 0, 1, 1, 2, 9, 9, 6, 1, 4, 8, 9, 0, 3, 0, 4, 6, 3, 9, 9, 4, 7, 1, 3, 2, 9, 6, 2, 1, 0, 7, 3, 4, 0,
346        4, 3, 7, 5, 1, 8, 9, 5, 7, 3, 5, 9, 6, 1, 4, 5, 8, 9, 0, 1, 9, 3, 8, 9, 7, 1, 3, 1, 1, 1, 7, 9, 0, 4, 2, 9, 7, 8, 2, 8, 5, 6, 4, 7, 5, 0, 3, 2, 0, 3, 1, 9, 8, 6, 9, 1, 5, 1, 4, 0, 2, 8, 7, 0, 8, 0, 8, 5, 9, 9,
347        0, 4, 8, 0, 1, 0, 9, 4, 1, 2, 1, 4, 7, 2, 2, 1, 3, 1, 7, 9, 4, 7, 6, 4, 7, 7, 7, 2, 6, 2, 2, 4, 1, 4, 2, 5, 4, 8, 5, 4, 5, 4, 0, 3, 3, 2, 1, 5, 7, 1, 8, 5, 3, 0, 6, 1, 4, 2, 2, 8, 8, 1, 3, 7, 5, 8, 5, 0, 4, 3,
348        0, 6, 3, 3, 2, 1, 7, 5, 1, 8, 2, 9, 7, 9, 8, 6, 6, 2, 2, 3, 7, 1, 7, 2, 1, 5, 9, 1, 6, 0, 7, 7, 1, 6, 6, 9, 2, 5, 4, 7, 4, 8, 7, 3, 8, 9, 8, 6, 6, 5, 4, 9, 4, 9, 4, 5, 0, 1, 1, 4, 6, 5, 4, 0, 6, 2, 8, 4, 3, 3,
349        6, 6, 3, 9, 3, 7, 9, 0, 0, 3, 9, 7, 6, 9, 2, 6, 5, 6, 7, 2, 1, 4, 6, 3, 8, 5, 3, 0, 6, 7, 3, 6, 0, 9, 6, 5, 7, 1, 2, 0, 9, 1, 8, 0, 7, 6, 3, 8, 3, 2, 7, 1, 6, 6, 4, 1, 6, 2, 7, 4, 8, 8, 8, 8, 0, 0, 7, 8, 6, 9,
350        2, 5, 6, 0, 2, 9, 0, 2, 2, 8, 4, 7, 2, 1, 0, 4, 0, 3, 1, 7, 2, 1, 1, 8, 6, 0, 8, 2, 0, 4, 1, 9, 0, 0, 0, 4, 2, 2, 9, 6, 6, 1, 7, 1, 1, 9, 6, 3, 7, 7, 9, 2, 1, 3, 3, 7, 5, 7, 5, 1, 1, 4, 9, 5, 9, 5, 0, 1, 5, 6,
351        6, 0, 4, 9, 6, 3, 1, 8, 6, 2, 9, 4, 7, 2, 6, 5, 4, 7, 3, 6, 4, 2, 5, 2, 3, 0, 8, 1, 7, 7, 0, 3, 6, 7, 5, 1, 5, 9, 0, 6, 7, 3, 5, 0, 2, 3, 5, 0, 7, 2, 8, 3, 5, 4, 0, 5, 6, 7, 0, 4, 0, 3, 8, 6, 7, 4, 3, 5, 1, 3,
352        6, 2, 2, 2, 2, 4, 7, 7, 1, 5, 8, 9, 1, 5, 0, 4, 9, 5, 3, 0, 9, 8, 4, 4, 4, 8, 9, 3, 3, 3, 0, 9, 6, 3, 4, 0, 8, 7, 8, 0, 7, 6, 9, 3, 2, 5, 9, 9, 3, 9, 7, 8, 0, 5, 4, 1, 9, 3, 4, 1, 4, 4, 7, 3, 7, 7, 4, 4, 1, 8,
353        4, 2, 6, 3, 1, 2, 9, 8, 6, 0, 8, 0, 9, 9, 8, 8, 8, 6, 8, 7, 4, 1, 3, 2, 6, 0, 4, 7, 2, 1, 5, 6, 9, 5, 1, 6, 2, 3, 9, 6, 5, 8, 6, 4, 5, 7, 3, 0, 2, 1, 6, 3, 1, 5, 9, 8, 1, 9, 3, 1, 9, 5, 1, 6, 7, 3, 5, 3, 8, 1,
354        2, 9, 7, 4, 1, 6, 7, 7, 2, 9, 4, 7, 8, 6, 7, 2, 4, 2, 2, 9, 2, 4, 6, 5, 4, 3, 6, 6, 8, 0, 0, 9, 8, 0, 6, 7, 6, 9, 2, 8, 2, 3, 8, 2, 8, 0, 6, 8, 9, 9, 6, 4, 0, 0, 4, 8, 2, 4, 3, 5, 4, 0, 3, 7, 0, 1, 4, 1, 6, 3,
355        1, 4, 9, 6, 5, 8, 9, 7, 9, 4, 0, 9, 2, 4, 3, 2, 3, 7, 8, 9, 6, 9, 0, 7, 0, 6, 9, 7, 7, 9, 4, 2, 2, 3, 6, 2, 5, 0, 8, 2, 2, 1, 6, 8, 8, 9, 5, 7, 3, 8, 3, 7, 9, 8, 6, 2, 3, 0, 0, 1, 5, 9, 3, 7, 7, 6, 4, 7, 1, 6,
356        5, 1, 2, 2, 8, 9, 3, 5, 7, 8, 6, 0, 1, 5, 8, 8, 1, 6, 1, 7, 5, 5, 7, 8, 2, 9, 7, 3, 5, 2, 3, 3, 4, 4, 6, 0, 4, 2, 8, 1, 5, 1, 2, 6, 2, 7, 2, 0, 3, 7, 3, 4, 3, 1, 4, 6, 5, 3, 1, 9, 7, 7, 7, 7, 4, 1, 6, 0, 3, 1,
357        9, 9, 0, 6, 6, 5, 5, 4, 1, 8, 7, 6, 3, 9, 7, 9, 2, 9, 3, 3, 4, 4, 1, 9, 5, 2, 1, 5, 4, 1, 3, 4, 1, 8, 9, 9, 4, 8, 5, 4, 4, 4, 7, 3, 4, 5, 6, 7, 3, 8, 3, 1, 6, 2, 4, 9, 9, 3, 4, 1, 9, 1, 3, 1, 8, 1, 4, 8, 0, 9,
358        2, 7, 7, 7, 7, 1, 0, 3, 8, 6, 3, 8, 7, 7, 3, 4, 3, 1, 7, 7, 2, 0, 7, 5, 4, 5, 6, 5, 4, 5, 3, 2, 2, 0, 7, 7, 7, 0, 9, 2, 1, 2, 0, 1, 9, 0, 5, 1, 6, 6, 0, 9, 6, 2, 8, 0, 4, 9, 0, 9, 2, 6, 3, 6, 0, 1, 9, 7, 5, 9,
359        8, 8, 2, 8, 1, 6, 1, 3, 3, 2, 3, 1, 6, 6, 6, 3, 6, 5, 2, 8, 6, 1, 9, 3, 2, 6, 6, 8, 6, 3, 3, 6, 0, 6, 2, 7, 3, 5, 6, 7, 6, 3, 0, 3, 5, 4, 4, 7, 7, 6, 2, 8, 0, 3, 5, 0, 4, 5, 0, 7, 7, 7, 2, 3, 5, 5, 4, 7, 1, 0,
360        5, 8, 5, 9, 5, 4, 8, 7, 0, 2, 7, 9, 0, 8, 1, 4, 3, 5, 6, 2, 4, 0, 1, 4, 5, 1, 7, 1, 8, 0, 6, 2, 4, 6, 4, 3, 6, 2, 6, 7, 9, 4, 5, 6, 1, 2, 7, 5, 3, 1, 8, 1, 3, 4, 0, 7, 8, 3, 3, 0, 3, 3, 6, 2, 5, 4, 2, 3, 2, 7,
361        8, 3, 9, 4, 4, 9, 7, 5, 3, 8, 2, 4, 3, 7, 2, 0, 5, 8, 3, 5, 3, 1, 1, 4, 7, 7, 1, 1, 9, 9, 2, 6, 0, 6, 3, 8, 1, 3, 3, 4, 6, 7, 7, 6, 8, 7, 9, 6, 9, 5, 9, 7, 0, 3, 0, 9, 8, 3, 3, 9, 1, 3, 0, 7, 7, 1, 0, 9, 8, 7,
362        0, 4, 0, 8, 5, 9, 1, 3, 3, 7, 4, 6, 4, 1, 4, 4, 2, 8, 2, 2, 7, 7, 2, 6, 3, 4, 6, 5, 9, 4, 7, 0, 4, 7, 4, 5, 8, 7, 8, 4, 7, 7, 8, 7, 2, 0, 1, 9, 2, 7, 7, 1, 5, 2, 8, 0, 7, 3, 1, 7, 6, 7, 9, 0, 7, 7, 0, 7, 1, 5,
363        7, 2, 1, 3, 4, 4, 4, 7, 3, 0, 6, 0, 5, 7, 0, 0, 7, 3, 3, 4, 9, 2, 4, 3, 6, 9, 3, 1, 1, 3, 8, 3, 5, 0, 4, 9, 3, 1, 6, 3, 1, 2, 8, 4, 0, 4, 2, 5, 1, 2, 1, 9, 2, 5, 6, 5, 1, 7, 9, 8, 0, 6, 9, 4, 1, 1, 3, 5, 2, 8,
364        0, 1, 3, 1, 4, 7, 0, 1, 3, 0, 4, 7, 8, 1, 6, 4, 3, 7, 8, 8, 5, 1, 8, 5, 2, 9, 0, 9, 2, 8, 5, 4, 5, 2, 0, 1, 1, 6, 5, 8, 3, 9, 3, 4, 1, 9, 6, 5, 6, 2, 1, 3, 4, 9, 1, 4, 3, 4, 1, 5, 9, 5, 6, 2, 5, 8, 6, 5, 8, 6,
365        5, 5, 7, 0, 5, 5, 2, 6, 9, 0, 4, 9, 6, 5, 2, 0, 9, 8, 5, 8, 0, 3, 3, 8, 5, 0, 7, 2, 2, 4, 2, 6, 4, 8, 2, 9, 3, 9, 7, 2, 8, 5, 8, 4, 7, 8, 3, 1, 6, 3, 0, 5, 7, 7, 7, 7, 5, 6, 0, 6, 8, 8, 8, 7, 6, 4, 4, 6, 2, 4,
366        8, 2, 4, 6, 8, 5, 7, 9, 2, 6, 0, 3, 9, 5, 3, 5, 2, 7, 7, 3, 4, 8, 0, 3, 0, 4, 8, 0, 2, 9, 0, 0, 5, 8, 7, 6, 0, 7, 5, 8, 2, 5, 1, 0, 4, 7, 4, 7, 0, 9, 1, 6, 4, 3, 9, 6, 1, 3, 6, 2, 6, 7, 6, 0, 4, 4, 9, 2, 5, 6,
367        2, 7, 4, 2, 0, 4, 2, 0, 8, 3, 2, 0, 8, 5, 6, 6, 1, 1, 9, 0, 6, 2, 5, 4, 5, 4, 3, 3, 7, 2, 1, 3, 1, 5, 3, 5, 9, 5, 8, 4, 5, 0, 6, 8, 7, 7, 2, 4, 6, 0, 2, 9, 0, 1, 6, 1, 8, 7, 6, 6, 7, 9, 5, 2, 4, 0, 6, 1, 6, 3,
368        4, 2, 5, 2, 2, 5, 7, 7, 1, 9, 5, 4, 2, 9, 1, 6, 2, 9, 9, 1, 9, 3, 0, 6, 4, 5, 5, 3, 7, 7, 9, 9, 1, 4, 0, 3, 7, 3, 4, 0, 4, 3, 2, 8, 7, 5, 2, 6, 2, 8, 8, 8, 9, 6, 3, 9, 9, 5, 8, 7, 9, 4, 7, 5, 7, 2, 9, 1, 7, 4,
369        6, 4, 2, 6, 3, 5, 7, 4, 5, 5, 2, 5, 4, 0, 7, 9, 0, 9, 1, 4, 5, 1, 3, 5, 7, 1, 1, 1, 3, 6, 9, 4, 1, 0, 9, 1, 1, 9, 3, 9, 3, 2, 5, 1, 9, 1, 0, 7, 6, 0, 2, 0, 8, 2, 5, 2, 0, 2, 6, 1, 8, 7, 9, 8, 5, 3, 1, 8, 8, 7,
370        7, 0, 5, 8, 4, 2, 9, 7, 2, 5, 9, 1, 6, 7, 7, 8, 1, 3, 1, 4, 9, 6, 9, 9, 0, 0, 9, 0, 1, 9, 2, 1, 1, 6, 9, 7, 1, 7, 3, 7, 2, 7, 8, 4, 7, 6, 8, 4, 7, 2, 6, 8, 6, 0, 8, 4, 9, 0, 0, 3, 3, 7, 7, 0, 2, 4, 2, 4, 2, 9,
371        1, 6, 5, 1, 3, 0, 0, 5, 0, 0, 5, 1, 6, 8, 3, 2, 3, 3, 6, 4, 3, 5, 0, 3, 8, 9, 5, 1, 7, 0, 2, 9, 8, 9, 3, 9, 2, 2, 3, 3, 4, 5, 1, 7, 2, 2, 0, 1, 3, 8, 1, 2, 8, 0, 6, 9, 6, 5, 0, 1, 1, 7, 8, 4, 4, 0, 8, 7, 4, 5,
372        1, 9, 6, 0, 1, 2, 1, 2, 2, 8, 5, 9, 9, 3, 7, 1, 6, 2, 3, 1, 3, 0, 1, 7, 1, 1, 4, 4, 4, 8, 4, 6, 4, 0, 9, 0, 3, 8, 9, 0, 6, 4, 4, 9, 5, 4, 4, 4, 0, 0, 6, 1, 9, 8, 6, 9, 0, 7, 5, 4, 8, 5, 1, 6, 0, 2, 6, 3, 2, 7,
373        5, 0, 5, 2, 9, 8, 3, 4, 9, 1, 8, 7, 4, 0, 7, 8, 6, 6, 8, 0, 8, 8, 1, 8, 3, 3, 8, 5, 1, 0, 2, 2, 8, 3, 3, 4, 5, 0, 8, 5, 0, 4, 8, 6, 0, 8, 2, 5, 0, 3, 9, 3, 0, 2, 1, 3, 3, 2, 1, 9, 7, 1, 5, 5, 1, 8, 4, 3, 0, 6,
374        3, 5, 4, 5, 5, 0, 0, 7, 6, 6, 8, 2, 8, 2, 9, 4, 9, 3, 0, 4, 1, 3, 7, 7, 6, 5, 5, 2, 7, 9, 3, 9, 7, 5, 1, 7, 5, 4, 6, 1, 3, 9, 5, 3, 9, 8, 4, 6, 8, 3, 3, 9, 3, 6, 3, 8, 3, 0, 4, 7, 4, 6, 1, 1, 9, 9, 6, 6, 5, 3,
375        8, 5, 8, 1, 5, 3, 8, 4, 2, 0, 5, 6, 8, 5, 3, 3, 8, 6, 2, 1, 8, 6, 7, 2, 5, 2, 3, 3, 4, 0, 2, 8, 3, 0, 8, 7, 1, 1, 2, 3, 2, 8, 2, 7, 8, 9, 2, 1, 2, 5, 0, 7, 7, 1, 2, 6, 2, 9, 4, 6, 3, 2, 2, 9, 5, 6, 3, 9, 8, 9,
376        8, 9, 8, 9, 3, 5, 8, 2, 1, 1, 6, 7, 4, 5, 6, 2, 7, 0, 1, 0, 2, 1, 8, 3, 5, 6, 4, 6, 2, 2, 0, 1, 3, 4, 9, 6, 7, 1, 5, 1, 8, 8, 1, 9, 0, 9, 7, 3, 0, 3, 8, 1, 1, 9, 8, 0, 0, 4, 9, 7, 3, 4, 0, 7, 2, 3, 9, 6, 1, 0,
377        3, 6, 8, 5, 4, 0, 6, 6, 4, 3, 1, 9, 3, 9, 5, 0, 9, 7, 9, 0, 1, 9, 0, 6, 9, 9, 6, 3, 9, 5, 5, 2, 4, 5, 3, 0, 0, 5, 4, 5, 0, 5, 8, 0, 6, 8, 5, 5, 0, 1, 9, 5, 6, 7, 3, 0, 2, 2, 9, 2, 1, 9, 1, 3, 9, 3, 3, 9, 1, 8,
378        5, 6, 8, 0, 3, 4, 4, 9, 0, 3, 9, 8, 2, 0, 5, 9, 5, 5, 1, 0, 0, 2, 2, 6, 3, 5, 3, 5, 3, 6, 1, 9, 2, 0, 4, 1, 9, 9, 4, 7, 4, 5, 5, 3, 8, 5, 9, 3, 8, 1, 0, 2, 3, 4, 3, 9, 5, 5, 4, 4, 9, 5, 9, 7, 7, 8, 3, 7, 7, 9,
379        0, 2, 3, 7, 4, 2, 1, 6, 1, 7, 2, 7, 1, 1, 1, 7, 2, 3, 6, 4, 3, 4, 3, 5, 4, 3, 9, 4, 7, 8, 2, 2, 1, 8, 1, 8, 5, 2, 8, 6, 2, 4, 0, 8, 5, 1, 4, 0, 0, 6, 6, 6, 0, 4, 4, 3, 3, 2, 5, 8, 8, 8, 5, 6, 9, 8, 6, 7, 0, 5,
380        4, 3, 1, 5, 4, 7, 0, 6, 9, 6, 5, 7, 4, 7, 4, 5, 8, 5, 5, 0, 3, 3, 2, 3, 2, 3, 3, 4, 2, 1, 0, 7, 3, 0, 1, 5, 4, 5, 9, 4, 0, 5, 1, 6, 5, 5, 3, 7, 9, 0, 6, 8, 6, 6, 2, 7, 3, 3, 3, 7, 9, 9, 5, 8, 5, 1, 1, 5, 6, 2,
381        5, 7, 8, 4, 3, 2, 2, 9, 8, 8, 2, 7, 3, 7, 2, 3, 1, 9, 8, 9, 8, 7, 5, 7, 1, 4, 1, 5, 9, 5, 7, 8, 1, 1, 1, 9, 6, 3, 5, 8, 3, 3, 0, 0, 5, 9, 4, 0, 8, 7, 3, 0, 6, 8, 1, 2, 1, 6, 0, 2, 8, 7, 6, 4, 9, 6, 2, 8, 6, 7,
382        4, 4, 6, 0, 4, 7, 7, 4, 6, 4, 9, 1, 5, 9, 9, 5, 0, 5, 4, 9, 7, 3, 7, 4, 2, 5, 6, 2, 6, 9, 0, 1, 0, 4, 9, 0, 3, 7, 7, 8, 1, 9, 8, 6, 8, 3, 5, 9, 3, 8, 1, 4, 6, 5, 7, 4, 1, 2, 6, 8, 0, 4, 9, 2, 5, 6, 4, 8, 7, 9,
383        8, 5, 5, 6, 1, 4, 5, 3, 7, 2, 3, 4, 7, 8, 6, 7, 3, 3, 0, 3, 9, 0, 4, 6, 8, 8, 3, 8, 3, 4, 3, 6, 3, 4, 6, 5, 5, 3, 7, 9, 4, 9, 8, 6, 4, 1, 9, 2, 7, 0, 5, 6, 3, 8, 7, 2, 9, 3, 1, 7, 4, 8, 7, 2, 3, 3, 2, 0, 8, 3,
384        7, 6, 0, 1, 1, 2, 3, 0, 2, 9, 9, 1, 1, 3, 6, 7, 9, 3, 8, 6, 2, 7, 0, 8, 9, 4, 3, 8, 7, 9, 9, 3, 6, 2, 0, 1, 6, 2, 9, 5, 1, 5, 4, 1, 3, 3, 7, 1, 4, 2, 4, 8, 9, 2, 8, 3, 0, 7, 2, 2, 0, 1, 2, 6, 9, 0, 1, 4, 7, 5,
385        4, 6, 6, 8, 4, 7, 6, 5, 3, 5, 7, 6, 1, 6, 4, 7, 7, 3, 7, 9, 4, 6, 7, 5, 2, 0, 0, 4, 9, 0, 7, 5, 7, 1, 5, 5, 5, 2, 7, 8, 1, 9, 6, 5, 3, 6, 2, 1, 3, 2, 3, 9, 2, 6, 4, 0, 6, 1, 6, 0, 1, 3, 6, 3, 5, 8, 1, 5, 5, 9,
386        0, 7, 4, 2, 2, 0, 2, 0, 2, 0, 3, 1, 8, 7, 2, 7, 7, 6, 0, 5, 2, 7, 7, 2, 1, 9, 0, 0, 5, 5, 6, 1, 4, 8, 4, 2, 5, 5, 5, 1, 8, 7, 9, 2, 5, 3, 0, 3, 4, 3, 5, 1, 3, 9, 8, 4, 4, 2, 5, 3, 2, 2, 3, 4, 1, 5, 7, 6, 2, 3,
387        3, 6, 1, 0, 6, 4, 2, 5, 0, 6, 3, 9, 0, 4, 9, 7, 5, 0, 0, 8, 6, 5, 6, 2, 7, 1, 0, 9, 5, 3, 5, 9, 1, 9, 4, 6, 5, 8, 9, 7, 5, 1, 4, 1, 3, 1, 0, 3, 4, 8, 2, 2, 7, 6, 9, 3, 0, 6, 2, 4, 7, 4, 3, 5, 3, 6, 3, 2, 5, 6,
388        9, 1, 6, 0, 7, 8, 1, 5, 4, 7, 8, 1, 8, 1, 1, 5, 2, 8, 4, 3, 6, 6, 7, 9, 5, 7, 0, 6, 1, 1, 0, 8, 6, 1, 5, 3, 3, 1, 5, 0, 4, 4, 5, 2, 1, 2, 7, 4, 7, 3, 9, 2, 4, 5, 4, 4, 9, 4, 5, 4, 2, 3, 6, 8, 2, 8, 8, 6, 0, 6,
389        1, 3, 4, 0, 8, 4, 1, 4, 8, 6, 3, 7, 7, 6, 7, 0, 0, 9, 6, 1, 2, 0, 7, 1, 5, 1, 2, 4, 9, 1, 4, 0, 4, 3, 0, 2, 7, 2, 5, 3, 8, 6, 0, 7, 6, 4, 8, 2, 3, 6, 3, 4, 1, 4, 3, 3, 4, 6, 2, 3, 5, 1, 8, 9, 7, 5, 7, 6, 6, 4,
390        5, 2, 1, 6, 4, 1, 3, 7, 6, 7, 9, 6, 9, 0, 3, 1, 4, 9, 5, 0, 1, 9, 1, 0, 8, 5, 7, 5, 9, 8, 4, 4, 2, 3, 9, 1, 9, 8, 6, 2, 9, 1, 6, 4, 2, 1, 9, 3, 9, 9, 4, 9, 0, 7, 2, 3, 6, 2, 3, 4, 6, 4, 6, 8, 4, 4, 1, 1, 7, 3,
391        9, 4, 0, 3, 2, 6, 5, 9, 1, 8, 4, 0, 4, 4, 3, 7, 8, 0, 5, 1, 3, 3, 3, 8, 9, 4, 5, 2, 5, 7, 4, 2, 3, 9, 9, 5, 0, 8, 2, 9, 6, 5, 9, 1, 2, 2, 8, 5, 0, 8, 5, 5, 5, 8, 2, 1, 5, 7, 2, 5, 0, 3, 1, 0, 7, 1, 2, 5, 7, 0,
392        1, 2, 6, 6, 8, 3, 0, 2, 4, 0, 2, 9, 2, 9, 5, 2, 5, 2, 2, 0, 1, 1, 8, 7, 2, 6, 7, 6, 7, 5, 6, 2, 2, 0, 4, 1, 5, 4, 2, 0, 5, 1, 6, 1, 8, 4, 1, 6, 3, 4, 8, 4, 7, 5, 6, 5, 1, 6, 9, 9, 9, 8, 1, 1, 6, 1, 4, 1, 0, 1,
393        0, 0, 2, 9, 9, 6, 0, 7, 8, 3, 8, 6, 9, 0, 9, 2, 9, 1, 6, 0, 3, 0, 2, 8, 8, 4, 0, 0, 2, 6, 9, 1, 0, 4, 1, 4, 0, 7, 9, 2, 8, 8, 6, 2, 1, 5, 0, 7, 8, 4, 2, 4, 5, 1, 6, 7, 0, 9, 0, 8, 7, 0, 0, 0, 6, 9, 9, 2, 8, 2,
394        1, 2, 0, 6, 6, 0, 4, 1, 8, 3, 7, 1, 8, 0, 6, 5, 3, 5, 5, 6, 7, 2, 5, 2, 5, 3, 2, 5, 6, 7, 5, 3, 2, 8, 6, 1, 2, 9, 1, 0, 4, 2, 4, 8, 7, 7, 6, 1, 8, 2, 5, 8, 2, 9, 7, 6, 5, 1, 5, 7, 9, 5, 9, 8, 4, 7, 0, 3, 5, 6,
395        2, 2, 2, 6, 2, 9, 3, 4, 8, 6, 0, 0, 3, 4, 1, 5, 8, 7, 2, 2, 9, 8, 0, 5, 3, 4, 9, 8, 9, 6, 5, 0, 2, 2, 6, 2, 9, 1, 7, 4, 8, 7, 8, 8, 2, 0, 2, 7, 3, 4, 2, 0, 9, 2, 2, 2, 2, 4, 5, 3, 3, 9, 8, 5, 6, 2, 6, 4, 7, 6,
396        6, 9, 1, 4, 9, 0, 5, 5, 6, 2, 8, 4, 2, 5, 0, 3, 9, 1, 2, 7, 5, 7, 7, 1, 0, 2, 8, 4, 0, 2, 7, 9, 9, 8, 0, 6, 6, 3, 6, 5, 8, 2, 5, 4, 8, 8, 9, 2, 6, 4, 8, 8, 0, 2, 5, 4, 5, 6, 6, 1, 0, 1, 7, 2, 9, 6, 7, 0, 2, 6,
397        6, 4, 0, 7, 6, 5, 5, 9, 0, 4, 2, 9, 0, 9, 9, 4, 5, 6, 8, 1, 5, 0, 6, 5, 2, 6, 5, 3, 0, 5, 3, 7, 1, 8, 2, 9, 4, 1, 2, 7, 0, 3, 3, 6, 9, 3, 1, 3, 7, 8, 5, 1, 7, 8, 6, 0, 9, 0, 4, 0, 7, 0, 8, 6, 6, 7, 1, 1, 4, 9,
398        6, 5, 5, 8, 3, 4, 3, 4, 3, 4, 7, 6, 9, 3, 3, 8, 5, 7, 8, 1, 7, 1, 1, 3, 8, 6, 4, 5, 5, 8, 7, 3, 6, 7, 8, 1, 2, 3, 0, 1, 4, 5, 8, 7, 6, 8, 7, 1, 2, 6, 6, 0, 3, 4, 8, 9, 1, 3, 9, 0, 9, 5, 6, 2, 0, 0, 9, 9, 3, 9,
399        3, 6, 1, 0, 3, 1, 0, 2, 9, 1, 6, 1, 6, 1, 5, 2, 8, 8, 1, 3, 8, 4, 3, 7, 9, 0, 9, 9, 0, 4, 2, 3, 1, 7, 4, 7, 3, 3, 6, 3, 9, 4, 8, 0, 4, 5, 7, 5, 9, 3, 1, 4, 9, 3, 1, 4, 0, 5, 2, 9, 7, 6, 3, 4, 7, 5, 7, 4, 8, 1,
400        1, 9, 3, 5, 6, 7, 0, 9, 1, 1, 0, 1, 3, 7, 7, 5, 1, 7, 2, 1, 0, 0, 8, 0, 3, 1, 5, 5, 9, 0, 2, 4, 8, 5, 3, 0, 9, 0, 6, 6, 9, 2, 0, 3, 7, 6, 7, 1, 9, 2, 2, 0, 3, 3, 2, 2, 9, 0, 9, 4, 3, 3, 4, 6, 7, 6, 8, 5, 1, 4,
401        2, 2, 1, 4, 4, 7, 7, 3, 7, 9, 3, 9, 3, 7, 5, 1, 7, 0, 3, 4, 4, 3, 6, 6, 1, 9, 9, 1, 0, 4, 0, 3, 3, 7, 5, 1, 1, 1, 7, 3, 5, 4, 7, 1, 9, 1, 8, 5, 5, 0, 4, 6, 4, 4, 9, 0, 2, 6, 3, 6, 5, 5, 1, 2, 8, 1, 6, 2, 2, 8,
402        8, 2, 4, 4, 6, 2, 5, 7, 5, 9, 1, 6, 3, 3, 3, 0, 3, 9, 1, 0, 7, 2, 2, 5, 3, 8, 3, 7, 4, 2, 1, 8, 2, 1, 4, 0, 8, 8, 3, 5, 0, 8, 6, 5, 7, 3, 9, 1, 7, 7, 1, 5, 0, 9, 6, 8, 2, 8, 8, 7, 4, 7, 8, 2, 6, 5, 6, 9, 9, 5,
403        9, 9, 5, 7, 4, 4, 9, 0, 6, 6, 1, 7, 5, 8, 3, 4, 4, 1, 3, 7, 5, 2, 2, 3, 9, 7, 0, 9, 6, 8, 3, 4, 0, 8, 0, 0, 5, 3, 5, 5, 9, 8, 4, 9, 1, 7, 5, 4, 1, 7, 3, 8, 1, 8, 8, 3, 9, 9, 9, 4, 4, 6, 9, 7, 4, 8, 6, 7, 6, 2,
404        6, 5, 5, 1, 6, 5, 8, 2, 7, 6, 5, 8, 4, 8, 3, 5, 8, 8, 4, 5, 3, 1, 4, 2, 7, 7, 5, 6, 8, 7, 9, 0, 0, 2, 9, 0, 9, 5, 1, 7, 0, 2, 8, 3, 5, 2, 9, 7, 1, 6, 3, 4, 4, 5, 6, 2, 1, 2, 9, 6, 4, 0, 4, 3, 5, 2, 3, 1, 1, 7,
405        6, 0, 0, 6, 6, 5, 1, 0, 1, 2, 4, 1, 2, 0, 0, 6, 5, 9, 7, 5, 5, 8, 5, 1, 2, 7, 6, 1, 7, 8, 5, 8, 3, 8, 2, 9, 2, 0, 4, 1, 9, 7, 4, 8, 4, 4, 2, 3, 6, 0, 8, 0, 0, 7, 1, 9, 3, 0, 4, 5, 7, 6, 1, 8, 9, 3, 2, 3, 4, 9,
406        2, 2, 9, 2, 7, 9, 6, 5, 0, 1, 9, 8, 7, 5, 1, 8, 7, 2, 1, 2, 7, 2, 6, 7, 5, 0, 7, 9, 8, 1, 2, 5, 5, 4, 7, 0, 9, 5, 8, 9, 0, 4, 5, 5, 6, 3, 5, 7, 9, 2, 1, 2, 2, 1, 0, 3, 3, 3, 4, 6, 6, 9, 7, 4, 9, 9, 2, 3, 5, 6,
407        3, 0, 2, 5, 4, 9, 4, 7, 8, 0, 2, 4, 9, 0, 1, 1, 4, 1, 9, 5, 2, 1, 2, 3, 8, 2, 8, 1, 5, 3, 0, 9, 1, 1, 4, 0, 7, 9, 0, 7, 3, 8, 6, 0, 2, 5, 1, 5, 2, 2, 7, 4, 2, 9, 9, 5, 8, 1, 8, 0, 7, 2, 4, 7, 1, 6, 2, 5, 9, 1,
408        6, 6, 8, 5, 4, 5, 1, 3, 3, 3, 1, 2, 3, 9, 4, 8, 0, 4, 9, 4, 7, 0, 7, 9, 1, 1, 9, 1, 5, 3, 2, 6, 7, 3, 4, 3, 0, 2, 8, 2, 4, 4, 1, 8, 6, 0, 4, 1, 4, 2, 6, 3, 6, 3, 9, 5, 4, 8, 0, 0, 0, 4, 4, 8, 0, 0, 2, 6, 7, 0,
409        4, 9, 6, 2, 4, 8, 2, 0, 1, 7, 9, 2, 8, 9, 6, 4, 7, 6, 6, 9, 7, 5, 8, 3, 1, 8, 3, 2, 7, 1, 3, 1, 4, 2, 5, 1, 7, 0, 2, 9, 6, 9, 2, 3, 4, 8, 8, 9, 6, 2, 7, 6, 6, 8, 4, 4, 0, 3, 2, 3, 2, 6, 0, 9, 2, 7, 5, 2, 4, 9,
410        6, 0, 3, 5, 7, 9, 9, 6, 4, 6, 9, 2, 5, 6, 5, 0, 4, 9, 3, 6, 8, 1, 8, 3, 6, 0, 9, 0, 0, 3, 2, 3, 8, 0, 9, 2, 9, 3, 4, 5,
411        9, 5, 8, 8, 9, 7, 0, 6, 9, 5, 3, 6, 5, 3, 4, 9, 4, 0, 6, 0, 3, 4, 0, 2, 1, 6, 6, 5, 4, 4, 3, 7, 5, 5, 8, 9, 0, 0, 4, 5, 6, 3, 2, 8, 8, 2, 2, 5, 0, 5, 4, 5, 2, 5, 5, 6, 4, 0, 5, 6, 4, 4, 8, 2, 4, 6, 5, 1, 5, 1,
412        8, 7, 5, 4, 7, 1, 1, 9, 6, 2, 1, 8, 4, 4, 3, 9, 6, 5, 8, 2, 5, 3, 3, 7, 5, 4, 3, 8, 8, 5, 6, 9, 0, 9, 4, 1, 1, 3, 0, 3, 1, 5, 0, 9, 5, 2, 6, 1, 7, 9, 3, 7, 8, 0, 0, 2, 9, 7, 4, 1, 2, 0, 7, 6, 6, 5, 1, 4, 7, 9,
413        3, 9, 4, 2, 5, 9, 0, 2, 9, 8, 9, 6, 9, 5, 9, 4, 6, 9, 9, 5, 5, 6, 5, 7, 6, 1, 2, 1, 8, 6, 5, 6, 1, 9, 6, 7, 3, 3, 7, 8, 6, 2, 3, 6, 2, 5, 6, 1, 2, 5, 2, 1, 6, 3, 2, 0, 8, 6, 2, 8, 6, 9, 2, 2, 2, 1, 0, 3, 2, 7,
414        4, 8, 8, 9, 2, 1, 8, 6, 5, 4, 3, 6, 4, 8, 0, 2, 2, 9, 6, 7, 8, 0, 7, 0, 5, 7, 6, 5, 6, 1, 5, 1, 4, 4, 6, 3, 2, 0, 4, 6, 9, 2, 7, 9, 0, 6, 8, 2, 1, 2, 0, 7, 3, 8, 8, 3, 7, 7, 8, 1, 4, 2, 3, 3, 5, 6, 2, 8, 2, 3,
415        6, 0, 8, 9, 6, 3, 2, 0, 8, 0, 6, 8, 2, 2, 2, 4, 6, 8, 0, 1, 2, 2, 4, 8, 2, 6, 1, 1, 7, 7, 1, 8, 5, 8, 9, 6, 3, 8, 1, 4, 0, 9, 1, 8, 3, 9, 0, 3, 6, 7, 3, 6, 7, 2, 2, 2, 0, 8, 8, 8, 3, 2, 1, 5, 1, 3, 7, 5, 5, 6,
416        0, 0, 3, 7, 2, 7, 9, 8, 3, 9, 4, 0, 0, 4, 1, 5, 2, 9, 7, 0, 0, 2, 8, 7, 8, 3, 0, 7, 6, 6, 7, 0, 9, 4, 4, 4, 7, 4, 5, 6, 0, 1, 3, 4, 5, 5, 6, 4, 1, 7, 2, 5, 4, 3, 7, 0, 9, 0, 6, 9, 7, 9, 3, 9, 6, 1, 2, 2, 5, 7,
417        1, 4, 2, 9, 8, 9, 4, 6, 7, 1, 5, 4, 3, 5, 7, 8, 4, 6, 8, 7, 8, 8, 6, 1, 4, 4, 4, 5, 8, 1, 2, 3, 1, 4, 5, 9, 3, 5, 7, 1, 9, 8, 4, 9, 2, 2, 5, 2, 8, 4, 7, 1, 6, 0, 5, 0, 4, 9, 2, 2, 1, 2, 4, 2, 4, 7, 0, 1, 4, 1,
418        2, 1, 4, 7, 8, 0, 5, 7, 3, 4, 5, 5, 1, 0, 5, 0, 0, 8, 0, 1, 9, 0, 8, 6, 9, 9, 6, 0, 3, 3, 0, 2, 7, 6, 3, 4, 7, 8, 7, 0, 8, 1, 0, 8, 1, 7, 5, 4, 5, 0, 1, 1, 9, 3, 0, 7, 1, 4, 1, 2, 2, 3, 3, 9, 0, 8, 6, 6, 3, 9,
419        3, 8, 3, 3, 9, 5, 2, 9, 4, 2, 5, 7, 8, 6, 9, 0, 5, 0, 7, 6, 4, 3, 1, 0, 0, 6, 3, 8, 3, 5, 1, 9, 8, 3, 4, 3, 8, 9, 3, 4, 1, 5, 9, 6, 1, 3, 1, 8, 5, 4, 3, 4, 7, 5, 4, 6, 4, 9, 5, 5, 6, 9, 7, 8, 1, 0, 3, 8, 2, 9,
420        3, 0, 9, 7, 1, 6, 4, 6, 5, 1, 4, 3, 8, 4, 0, 7, 0, 0, 7, 0, 7, 3, 6, 0, 4, 1, 1, 2, 3, 7, 3, 5, 9, 9, 8, 4, 3, 4, 5, 2, 2, 5, 1, 6, 1, 0, 5, 0, 7, 0, 2, 7, 0, 5, 6, 2, 3, 5, 2, 6, 6, 0, 1, 2, 7, 6, 4, 8, 4, 8,
421        3, 0, 8, 4, 0, 7, 6, 1, 1, 8, 3, 0, 1, 3, 0, 5, 2, 7, 9, 3, 2, 0, 5, 4, 2, 7, 4, 6, 2, 8, 6, 5, 4, 0, 3, 6, 0, 3, 6, 7, 4, 5, 3, 2, 8, 6, 5, 1, 0, 5, 7, 0, 6, 5, 8, 7, 4, 8, 8, 2, 2, 5, 6, 9, 8, 1, 5, 7, 9, 3,
422        6, 7, 8, 9, 7, 6, 6, 9, 7, 4, 2, 2, 0, 5, 7, 5, 0, 5, 9, 6, 8, 3, 4, 4, 0, 8, 6, 9, 7, 3, 5, 0, 2, 0, 1, 4, 1, 0, 2, 0, 6, 7, 2, 3, 5, 8, 5, 0, 2, 0, 0, 7, 2, 4, 5, 2, 2, 5, 6, 3, 2, 6, 5, 1, 3, 4, 1, 0, 5, 5,
423        9, 2, 4, 0, 1, 9, 0, 2, 7, 4, 2, 1, 6, 2, 4, 8, 4, 3, 9, 1, 4, 0, 3, 5, 9, 9, 8, 9, 5, 3, 5, 3, 9, 4, 5, 9, 0, 9, 4, 4, 0, 7, 0, 4, 6, 9, 1, 2, 0, 9, 1, 4, 0, 9, 3, 8, 7, 0, 0, 1, 2, 6, 4, 5, 6, 0, 0, 1, 6, 2,
424        3, 7, 4, 2, 8, 8, 0, 2, 1, 0, 9, 2, 7, 6, 4, 5, 7, 9, 3, 1, 0, 6, 5, 7, 9, 2, 2, 9, 5, 5, 2, 4, 9, 8, 8, 7, 2, 7, 5, 8, 4, 6, 1, 0, 1, 2, 6, 4, 8, 3, 6, 9, 9, 9, 8, 9, 2, 2, 5, 6, 9, 5, 9, 6, 8, 8, 1, 5, 9, 2,
425        0, 5, 6, 0, 0, 1, 0, 1, 6, 5, 5, 2, 5, 6, 3, 7, 5, 6, 7, 8
426    };
427}
428