[Geofence] Update SatS2FileCreator, SatS2LocationLookup, and DumpSatS2File to support config ID
Bug: 377610777
Flag: EXEMPT refactor
Test: atest CreateSatS2FileTest
Test: manualy run satellite_createsats2file_test to create the
sats2.data file then verify the file info using satellite_dumpsats2file
as below
satellite_createsats2file_test ~/work/test/s2sat.dat
satellite_dumpsats2file ~/work/test/s2sat.dat ~/work/test/outputdump/
dump file was uploaded in https://b.corp.google.com/issues/377610777#comment2
Test: manual system test for Skylo using Pixel
Change-Id: I268b7ddab7582e7a766d9e26a98685d6931312b2
diff --git a/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/PopulatedSuffixTableBlock.java b/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/PopulatedSuffixTableBlock.java
index 8cb9d1d..1eb66ac 100644
--- a/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/PopulatedSuffixTableBlock.java
+++ b/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/PopulatedSuffixTableBlock.java
@@ -88,6 +88,16 @@
return mPackedTable.getEntryCount();
}
+ @Override
+ public int getEntryValueCount() {
+ return mSuffixTableSharedData.getNumberOfEntryValues();
+ }
+
+ @Override
+ public int getEntryValue(int index) {
+ return mSuffixTableSharedData.getEntryValue(index);
+ }
+
/**
* Returns an entry that matches the supplied matcher. If multiple entries match, an arbitrary
* matching entry is returned. If no entries match then {@code null} is returned.
diff --git a/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/SuffixTableBlock.java b/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/SuffixTableBlock.java
index ffd28d5..0ee4f78 100644
--- a/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/SuffixTableBlock.java
+++ b/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/SuffixTableBlock.java
@@ -82,6 +82,12 @@
/** Returns the number of entries in the table. */
int getEntryCount();
+
+ /** Returns the number of entry values from the shared data. */
+ int getEntryValueCount();
+
+ /** Returns the entry value from the shared data for the given index. */
+ int getEntryValue(int index);
}
private SuffixTableBlock(SatS2RangeFileFormat fileFormat, SuffixTableBlockDelegate delegate) {
@@ -150,6 +156,16 @@
return mDelegate.getEntryCount();
}
+ /** Returns the number of entry values from the shared data. */
+ public int getEntryValueCount() {
+ return mDelegate.getEntryValueCount();
+ }
+
+ /** Returns the entry value from the shared data for the given index. */
+ public int getEntryValue(int index) {
+ return mDelegate.getEntryValue(index);
+ }
+
/** A {@link Visitor} for the {@link SuffixTableBlock}. See {@link #visit} */
public interface SuffixTableBlockVisitor extends Visitor {
diff --git a/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/UnpopulatedSuffixTableBlock.java b/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/UnpopulatedSuffixTableBlock.java
index 56730c2..c8ccb6b 100644
--- a/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/UnpopulatedSuffixTableBlock.java
+++ b/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/UnpopulatedSuffixTableBlock.java
@@ -16,6 +16,8 @@
package com.android.telephony.sats2range.read;
+import static com.android.telephony.sats2range.read.SuffixTableSharedData.INVALID_ENTRY_VALUE;
+
/**
* An implementation of {@link SuffixTableBlock.SuffixTableBlockDelegate} for tables that are not
* backed by real block data, i.e. have zero entries.
@@ -47,4 +49,16 @@
public int getEntryCount() {
return 0;
}
+
+ /** Returns the number of entry values from the shared data. */
+ @Override
+ public int getEntryValueCount() {
+ return 0;
+ }
+
+ /** Returns the entry value from the shared data for the given index. */
+ @Override
+ public int getEntryValue(int index) {
+ return INVALID_ENTRY_VALUE;
+ }
}
diff --git a/utils/satellite/s2storage/src/testutils/java/com/android/telephony/sats2range/testutils/TestUtils.java b/utils/satellite/s2storage/src/testutils/java/com/android/telephony/sats2range/testutils/TestUtils.java
index ca0b754..a7e7d0b 100644
--- a/utils/satellite/s2storage/src/testutils/java/com/android/telephony/sats2range/testutils/TestUtils.java
+++ b/utils/satellite/s2storage/src/testutils/java/com/android/telephony/sats2range/testutils/TestUtils.java
@@ -19,22 +19,26 @@
import static com.android.storage.s2.S2Support.FACE_BIT_COUNT;
import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.fail;
import com.android.storage.util.BitwiseUtils;
import com.android.telephony.sats2range.read.SatS2RangeFileFormat;
import java.io.File;
import java.io.IOException;
+import java.io.InputStream;
import java.io.PrintStream;
import java.nio.file.FileVisitResult;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.SimpleFileVisitor;
+import java.nio.file.StandardCopyOption;
import java.nio.file.attribute.BasicFileAttributes;
/** A utility class for satellite tests */
public class TestUtils {
public static final int TEST_S2_LEVEL = 12;
+ public static final String TEST_DATA_RESOURCE_DIR = "data/";
/** Returns a valid {@link SatS2RangeFileFormat}. */
public static SatS2RangeFileFormat createS2RangeFileFormat(boolean isAllowedList) {
@@ -86,6 +90,31 @@
return fileFormat.createCellId(prefixValue, suffixBits);
}
+ /**
+ * Copy a test resource to the target directory.
+ */
+ public static Path copyTestResource(Class<?> baseClass, String testResource, Path targetDir)
+ throws IOException {
+ Files.createDirectories(targetDir);
+ return copyResource(baseClass, TEST_DATA_RESOURCE_DIR + testResource, targetDir);
+ }
+
+ private static Path copyResource(Class<?> baseClass, String relativeResourcePath,
+ Path targetDir) throws IOException {
+ String fileName = relativeResourcePath;
+ if (relativeResourcePath.contains("/")) {
+ fileName = relativeResourcePath.substring(relativeResourcePath.lastIndexOf('/') + 1);
+ }
+ Path targetResourceFile = targetDir.resolve(fileName);
+ try (InputStream inputStream = baseClass.getResourceAsStream(relativeResourcePath)) {
+ if (inputStream == null) {
+ fail("Resource=" + relativeResourcePath + " not found");
+ }
+ Files.copy(inputStream, targetResourceFile, StandardCopyOption.REPLACE_EXISTING);
+ }
+ return targetResourceFile;
+ }
+
/** Create a temporary directory */
public static Path createTempDir(Class<?> testClass) throws IOException {
return Files.createTempDirectory(testClass.getSimpleName());
@@ -116,21 +145,19 @@
try (PrintStream printer = new PrintStream(outputFile)) {
// Range 1
for (int suffix = 1000; suffix < 2000; suffix++) {
- printer.println(fileFormat.createCellId(0b100_11111111, suffix));
+ printer.println(fileFormat.createCellId(0b100_11111111, suffix) + ",1");
}
// Range 2
for (int suffix = 2001; suffix < 3000; suffix++) {
- printer.println(fileFormat.createCellId(0b100_11111111, suffix));
+ printer.println(fileFormat.createCellId(0b100_11111111, suffix) + ",2");
}
// Range 3
for (int suffix = 1000; suffix < 2000; suffix++) {
- printer.println(fileFormat.createCellId(0b101_11111111, suffix));
+ printer.println(fileFormat.createCellId(0b101_11111111, suffix) + ",3");
}
- printer.print(fileFormat.createCellId(0b101_11111111, 2000));
-
- printer.close();
+ printer.print(fileFormat.createCellId(0b101_11111111, 2000) + ",3");
}
}
@@ -139,15 +166,41 @@
File outputFile, SatS2RangeFileFormat fileFormat) throws Exception {
try (PrintStream printer = new PrintStream(outputFile)) {
// Valid line
- printer.println(fileFormat.createCellId(0b100_11111111, 100));
+ printer.println(fileFormat.createCellId(0b100_11111111, 100) + ",0");
// Invalid line
printer.print("Invalid line");
// Another valid line
- printer.println(fileFormat.createCellId(0b100_11111111, 200));
+ printer.println(fileFormat.createCellId(0b100_11111111, 200) + ",1");
+ }
+ }
- printer.close();
+ /** Create a valid test satellite S2 cell file */
+ public static void createValidTestS2CellFileWithValidEntryValue(
+ File outputFile, SatS2RangeFileFormat fileFormat) throws Exception {
+
+ try (PrintStream printer = new PrintStream(outputFile)) {
+ // Range 1
+ for (int suffix = 1000; suffix < 1500; suffix++) {
+ printer.println(fileFormat.createCellId(0b100_11111111, suffix) + ",1");
+ }
+
+ // Range 2
+ for (int suffix = 1500; suffix < 2000; suffix++) {
+ printer.println(fileFormat.createCellId(0b100_11111111, suffix) + ",2");
+ }
+
+ // Range 3
+ for (int suffix = 2001; suffix < 3000; suffix++) {
+ printer.println(fileFormat.createCellId(0b100_11111111, suffix) + ",3");
+ }
+
+ // Range 4
+ for (int suffix = 1000; suffix < 2000; suffix++) {
+ printer.println(fileFormat.createCellId(0b101_11111111, suffix) + ",4");
+ }
+ printer.print(fileFormat.createCellId(0b101_11111111, 2000) + ",4");
}
}
}
diff --git a/utils/satellite/s2storage/src/write/java/com/android/telephony/sats2range/write/SatS2RangeFileWriter.java b/utils/satellite/s2storage/src/write/java/com/android/telephony/sats2range/write/SatS2RangeFileWriter.java
index 375707a..1827a96 100644
--- a/utils/satellite/s2storage/src/write/java/com/android/telephony/sats2range/write/SatS2RangeFileWriter.java
+++ b/utils/satellite/s2storage/src/write/java/com/android/telephony/sats2range/write/SatS2RangeFileWriter.java
@@ -93,6 +93,7 @@
List<SuffixTableRange> samePrefixRanges = new ArrayList<>();
while (pushBackIterator.hasNext()) {
SuffixTableRange currentRange = pushBackIterator.next();
+ int entryValue = currentRange.getEntryValue();
long startCellId = currentRange.getStartCellId();
if (mFileFormat.getS2Level() != S2Support.getS2Level(startCellId)) {
@@ -123,7 +124,8 @@
// Create a range for the current prefix.
{
long newEndCellId = mFileFormat.createCellId(startCellPrefix + 1, 0);
- SuffixTableRange satS2Range = new SuffixTableRange(startCellId, newEndCellId);
+ SuffixTableRange satS2Range = new SuffixTableRange(startCellId, newEndCellId,
+ entryValue);
samePrefixRanges.add(satS2Range);
}
@@ -134,7 +136,7 @@
long newStartCellId = mFileFormat.createCellId(startCellPrefix, 0);
long newEndCellId = mFileFormat.createCellId(startCellPrefix + 1, 0);
SuffixTableRange satS2Range = new SuffixTableRange(newStartCellId,
- newEndCellId);
+ newEndCellId, entryValue);
otherRanges.add(satS2Range);
startCellPrefix++;
}
@@ -144,7 +146,7 @@
long newStartCellId = mFileFormat.createCellId(endCellPrefixValue, 0);
if (newStartCellId != endCellId) {
SuffixTableRange satS2Range = new SuffixTableRange(newStartCellId,
- endCellId);
+ endCellId, entryValue);
otherRanges.add(satS2Range);
}
}
diff --git a/utils/satellite/tools/Android.bp b/utils/satellite/tools/Android.bp
index d48b911..b7b5dec 100644
--- a/utils/satellite/tools/Android.bp
+++ b/utils/satellite/tools/Android.bp
@@ -70,11 +70,12 @@
java_test_host {
name: "SatelliteToolsTests",
srcs: ["src/test/java/**/*.java"],
+ java_resource_dirs: ["src/test/java/"],
static_libs: [
"junit",
"satellite-s2storage-tools",
"s2-geometry-library-java",
- "satellite-s2storage-testutils"
+ "satellite-s2storage-testutils",
],
test_suites: ["general-tests"],
-}
\ No newline at end of file
+}
diff --git a/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/CreateSatS2File.java b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/CreateSatS2File.java
index f82cd5c..2db1d4e 100644
--- a/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/CreateSatS2File.java
+++ b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/CreateSatS2File.java
@@ -37,7 +37,11 @@
int s2Level = arguments.s2Level;
String outputFile = arguments.outputFile;
boolean isAllowedList = Arguments.getBooleanValue(arguments.isAllowedList);
- SatS2FileCreator.create(inputFile, s2Level, isAllowedList, outputFile);
+ int entryValueSizeInBytes = Arguments.validateEntryValueSize(isAllowedList,
+ arguments.entryValueSizeInBytes);
+ int versionNumber = arguments.versionNumber;
+ SatS2FileCreator.create(inputFile, s2Level, isAllowedList, entryValueSizeInBytes,
+ versionNumber, outputFile);
}
private static class Arguments {
@@ -56,6 +60,14 @@
required = true)
public String isAllowedList;
+ @Parameter(names = "--entry-value-byte-size",
+ description = "byte size length for entry values")
+ public int entryValueSizeInBytes;
+
+ @Parameter(names = "--version-number",
+ description = "version number for header block")
+ public int versionNumber;
+
@Parameter(names = "--output-file",
description = "sat s2 file",
required = true)
@@ -68,5 +80,16 @@
throw new ParameterException("Invalid boolean string:" + value);
}
}
+
+ public static int validateEntryValueSize(boolean isAllowedList, int entryValueSizeInBytes) {
+ if (entryValueSizeInBytes < 0
+ || (!isAllowedList && entryValueSizeInBytes > 0)
+ || entryValueSizeInBytes > 4) {
+ throw new IllegalArgumentException(
+ "Invalid entryValueSizeInBytes: " + entryValueSizeInBytes
+ + ", isAllowedList: " + isAllowedList);
+ }
+ return entryValueSizeInBytes;
+ }
}
}
diff --git a/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/CreateTestSatS2File.java b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/CreateTestSatS2File.java
index 41ce416..0bda4ec 100644
--- a/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/CreateTestSatS2File.java
+++ b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/CreateTestSatS2File.java
@@ -26,6 +26,10 @@
/** Creates a Sat S2 file with a small amount of test data. Useful for testing other tools. */
public final class CreateTestSatS2File {
+ private static final int S2_LEVEL = 12;
+ private static final boolean IS_ALLOWED_LIST = true;
+ private static final int ENTRY_VALUE_BYTE_SIZE = 4;
+ private static final int VERSION_NUMBER = 1;
/**
* Usage:
@@ -34,7 +38,8 @@
public static void main(String[] args) throws Exception {
File file = new File(args[0]);
- SatS2RangeFileFormat fileFormat = FileFormats.getFileFormatForLevel(12, true);
+ SatS2RangeFileFormat fileFormat = FileFormats.getFileFormatForLevel(S2_LEVEL,
+ IS_ALLOWED_LIST, ENTRY_VALUE_BYTE_SIZE, VERSION_NUMBER);
if (fileFormat.getPrefixBitCount() != 11) {
throw new IllegalStateException("Fake data requires 11 prefix bits");
}
@@ -44,15 +49,18 @@
// Two ranges that share a prefix.
SuffixTableRange range1 = new SuffixTableRange(
fileFormat.createCellId(0b100_11111111, 1000),
- fileFormat.createCellId(0b100_11111111, 2000));
+ fileFormat.createCellId(0b100_11111111, 2000),
+ 1);
SuffixTableRange range2 = new SuffixTableRange(
fileFormat.createCellId(0b100_11111111, 2000),
- fileFormat.createCellId(0b100_11111111, 3000));
+ fileFormat.createCellId(0b100_11111111, 3000),
+ 2);
// This range has a different face, so a different prefix, and will be in a different
// suffix table.
SuffixTableRange range3 = new SuffixTableRange(
fileFormat.createCellId(0b101_11111111, 1000),
- fileFormat.createCellId(0b101_11111111, 2000));
+ fileFormat.createCellId(0b101_11111111, 2000),
+ 3);
List<SuffixTableRange> allRanges = listOf(range1, range2, range3);
satS2RangeFileWriter.createSortedSuffixBlocks(allRanges.iterator());
}
diff --git a/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/FileFormats.java b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/FileFormats.java
index b800897..32e6f48 100644
--- a/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/FileFormats.java
+++ b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/FileFormats.java
@@ -56,4 +56,19 @@
+ ", isAllowedList=" + isAllowedList + " not mapped");
}
}
+
+ /** Maps an S2 level to one of the file format constants declared on by class. */
+ public static SatS2RangeFileFormat getFileFormatForLevel(int s2Level, boolean isAllowedList,
+ int entryValueSizeInBytes, int versionNumber) {
+ SatS2RangeFileFormat fileFormat = getFileFormatForLevel(s2Level, isAllowedList);
+ return new SatS2RangeFileFormat(
+ fileFormat.getS2Level(),
+ fileFormat.getPrefixBitCount(),
+ fileFormat.getSuffixBitCount(),
+ fileFormat.getSuffixTableBlockIdOffset(),
+ fileFormat.getTableEntryBitCount(),
+ fileFormat.isAllowedList(),
+ entryValueSizeInBytes,
+ versionNumber);
+ }
}
diff --git a/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/SatS2FileCreator.java b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/SatS2FileCreator.java
index 1ed9680..74c4011 100644
--- a/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/SatS2FileCreator.java
+++ b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/SatS2FileCreator.java
@@ -29,21 +29,22 @@
import java.io.InputStream;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
-import java.util.Collections;
-import java.util.HashSet;
+import java.util.Comparator;
+import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
+import java.util.Map;
import java.util.Objects;
import java.util.Scanner;
-import java.util.Set;
import java.util.concurrent.TimeUnit;
/** A util class for creating a satellite S2 file from the list of S2 cells. */
public final class SatS2FileCreator {
/**
* @param inputFile The input text file containing the list of S2 Cell IDs. Each line in the
- * file contains a number in the range of a 64-bit number which represents the
- * ID of a S2 cell.
+ * file contains two numbers separated by a comma. The first number is in the
+ * range of a 64bit number which represents the ID of a S2 cell. The second
+ * number is satellite access config ID for the S2 cell.
* @param s2Level The S2 level of all S2 cells in the input file.
* @param isAllowedList {@code true} means the input file contains an allowed list of S2 cells.
* {@code false} means the input file contains a disallowed list of S2
@@ -52,30 +53,32 @@
* written.
*/
public static void create(String inputFile, int s2Level, boolean isAllowedList,
- String outputFile) throws Exception {
+ int entryValueSizeInBytes, int versionNumber, String outputFile) throws Exception {
// Read a list of S2 cells from input file
- List<Long> s2Cells = readS2CellsFromFile(inputFile);
+ List<Pair<Long, Integer>> s2Cells = readS2CellsFromFile(inputFile);
System.out.println("Number of S2 cells read from file:" + s2Cells.size());
// Convert the input list of S2 Cells into the list of sorted S2CellId
System.out.println("Denormalizing S2 Cell IDs to the expected s2 level=" + s2Level);
- List<S2CellId> sortedS2CellIds = denormalize(s2Cells, s2Level);
+ List<Pair<S2CellId, Integer>> sortedS2CellIds = normalize(s2Cells, s2Level);
+
// IDs of S2CellId are converted to unsigned long numbers, which will be then used to
// compare S2CellId.
- Collections.sort(sortedS2CellIds);
+ sortedS2CellIds.sort(Comparator.comparing(o -> o.first));
System.out.println("Number of S2 cell IDs:" + sortedS2CellIds.size());
// Compress the list of S2CellId into S2 ranges
List<SatS2Range> satS2Ranges = createSatS2Ranges(sortedS2CellIds, s2Level);
// Write the S2 ranges into a block file
- SatS2RangeFileFormat fileFormat =
- FileFormats.getFileFormatForLevel(s2Level, isAllowedList);
+ SatS2RangeFileFormat fileFormat = FileFormats.getFileFormatForLevel(s2Level, isAllowedList,
+ entryValueSizeInBytes, versionNumber);
try (SatS2RangeFileWriter satS2RangeFileWriter =
SatS2RangeFileWriter.open(new File(outputFile), fileFormat)) {
Iterator<SuffixTableRange> suffixTableRangeIterator = satS2Ranges
.stream()
- .map(x -> new SuffixTableRange(x.rangeStart.id(), x.rangeEnd.id()))
+ .map(x -> new SuffixTableRange(x.rangeStart.id(), x.rangeEnd.id(),
+ x.entryValue))
.iterator();
/*
* Group the sorted ranges into contiguous suffix blocks. Big ranges might get split as
@@ -94,18 +97,26 @@
+ "argument=" + isAllowedList);
}
- // Verify that all input S2 cells are present in the output block file
- for (S2CellId s2CellId : sortedS2CellIds) {
- if (satS2RangeFileReader.findEntryByCellId(s2CellId.id()) == null) {
- throw new IllegalStateException("s2CellId=" + s2CellId
+ // Verify that all input S2 cells are present in the output block file and the their
+ // entry value matches the provided entry value
+ for (Pair<S2CellId, Integer> s2CellInfo : sortedS2CellIds) {
+ SuffixTableRange entry =
+ satS2RangeFileReader.findEntryByCellId(s2CellInfo.first.id());
+ if (entry == null) {
+ throw new IllegalStateException("s2CellInfo=" + s2CellInfo
+ " is not present in the output sat s2 file");
+ } else if (entry.getEntryValue() != s2CellInfo.second) {
+ throw new IllegalStateException("entry.getEntryValue=" + entry.getEntryValue()
+ + " does not match the provided entry value=" + s2CellInfo.second);
}
}
// Verify the cell right before the first cell in the sortedS2CellIds is not present in
// the output block file
- S2CellId prevCell = sortedS2CellIds.get(0).prev();
- if (!sortedS2CellIds.contains(prevCell)
+ S2CellId prevCell = sortedS2CellIds.getFirst().first.prev();
+ boolean containsPrevCell = sortedS2CellIds.stream()
+ .anyMatch(pair -> pair.first.equals(prevCell));
+ if (!containsPrevCell
&& satS2RangeFileReader.findEntryByCellId(prevCell.id()) != null) {
throw new IllegalStateException("The cell " + prevCell + ", which is right "
+ "before the first cell is unexpectedly present in the output sat s2"
@@ -116,8 +127,10 @@
// Verify the cell right after the last cell in the sortedS2CellIds is not present in
// the output block file
- S2CellId nextCell = sortedS2CellIds.get(sortedS2CellIds.size() - 1).next();
- if (!sortedS2CellIds.contains(nextCell)
+ S2CellId nextCell = sortedS2CellIds.getLast().first.next();
+ boolean containsNextCell = sortedS2CellIds.stream()
+ .anyMatch(pair -> pair.first.equals(nextCell));
+ if (!containsNextCell
&& satS2RangeFileReader.findEntryByCellId(nextCell.id()) != null) {
throw new IllegalStateException("The cell " + nextCell + ", which is right "
+ "after the last cell is unexpectedly present in the output sat s2"
@@ -136,17 +149,24 @@
* a 64-bit number - the ID of a S2 cell.
* @return A list of S2 cells.
*/
- private static List<Long> readS2CellsFromFile(String inputFile) throws Exception {
- List<Long> s2Cells = new ArrayList();
+ private static List<Pair<Long, Integer>> readS2CellsFromFile(String inputFile)
+ throws Exception {
+ List<Pair<Long, Integer>> s2Cells = new ArrayList<>();
InputStream inputStream = new FileInputStream(inputFile);
- try (Scanner scanner = new Scanner(inputStream, StandardCharsets.UTF_8.name())) {
+ try (Scanner scanner = new Scanner(inputStream, StandardCharsets.UTF_8)) {
while (scanner.hasNextLine()) {
String line = scanner.nextLine();
+ String[] s2CellInfoStrs = line.split(",");
+ if (s2CellInfoStrs == null || s2CellInfoStrs.length != 2) {
+ throw new IllegalStateException("The Input s2 cell file has invalid format, "
+ + "current line=" + line);
+ }
try {
- s2Cells.add(Long.parseLong(line));
+ s2Cells.add(new Pair<>(Long.parseLong(s2CellInfoStrs[0]),
+ Integer.parseUnsignedInt(s2CellInfoStrs[1])));
} catch (Exception ex) {
throw new IllegalStateException("Input s2 cell file has invalid format, "
- + "current line=" + line);
+ + "current line=" + line + ", ex=" + ex);
}
}
}
@@ -156,30 +176,36 @@
/**
* Convert the list of S2 Cell numbers into the list of S2 Cell IDs at the expected level.
*/
- private static List<S2CellId> denormalize(List<Long> s2CellNumbers, int s2Level) {
- Set<S2CellId> result = new HashSet<>();
- for (long s2CellNumber : s2CellNumbers) {
- S2CellId s2CellId = new S2CellId(s2CellNumber);
+ private static List<Pair<S2CellId, Integer>> normalize(
+ List<Pair<Long, Integer>> s2CellNumbers, int s2Level) {
+ Map<S2CellId, Integer> s2CellIdMap = new HashMap<>();
+ for (Pair<Long, Integer> s2CellInfo : s2CellNumbers) {
+ S2CellId s2CellId = new S2CellId(s2CellInfo.first);
if (s2CellId.level() == s2Level) {
- if (!result.contains(s2CellId)) {
- result.add(s2CellId);
+ if (!s2CellIdMap.containsKey(s2CellId)) {
+ s2CellIdMap.put(s2CellId, s2CellInfo.second);
}
} else if (s2CellId.level() < s2Level) {
S2CellId childEnd = s2CellId.childEnd(s2Level);
for (s2CellId = s2CellId.childBegin(s2Level); !s2CellId.equals(childEnd);
s2CellId = s2CellId.next()) {
- if (!result.contains(s2CellId)) {
- result.add(s2CellId);
+ if (!s2CellIdMap.containsKey(s2CellId)) {
+ s2CellIdMap.put(s2CellId, s2CellInfo.second);
}
}
} else {
S2CellId parent = s2CellId.parent(s2Level);
- if (!result.contains(parent)) {
- result.add(parent);
+ if (!s2CellIdMap.containsKey(parent)) {
+ s2CellIdMap.put(parent, s2CellInfo.second);
}
}
}
- return new ArrayList(result);
+
+ List<Pair<S2CellId, Integer>> result = new ArrayList();
+ for (Map.Entry<S2CellId, Integer> entry : s2CellIdMap.entrySet()) {
+ result.add(new Pair<>(entry.getKey(), entry.getValue()));
+ }
+ return result;
}
/**
@@ -189,32 +215,38 @@
* @param s2Level The level of all S2CellId.
* @return List of S2 ranges.
*/
- private static List<SatS2Range> createSatS2Ranges(List<S2CellId> sortedS2CellIds, int s2Level) {
+ private static List<SatS2Range> createSatS2Ranges(List<Pair<S2CellId, Integer>> sortedS2CellIds,
+ int s2Level) {
Stopwatch stopwatch = Stopwatch.createStarted();
List<SatS2Range> ranges = new ArrayList<>();
- if (sortedS2CellIds != null && sortedS2CellIds.size() > 0) {
+ if (sortedS2CellIds != null && !sortedS2CellIds.isEmpty()) {
S2CellId rangeStart = null;
S2CellId rangeEnd = null;
+ int rangeEntryValue = 0;
for (int i = 0; i < sortedS2CellIds.size(); i++) {
- S2CellId currentS2CellId = sortedS2CellIds.get(i);
+ S2CellId currentS2CellId = sortedS2CellIds.get(i).first;
checkCellIdIsAtLevel(currentS2CellId, s2Level);
- SatS2Range currentRange = createS2Range(currentS2CellId, s2Level);
+ SatS2Range currentRange = createS2Range(currentS2CellId, s2Level,
+ sortedS2CellIds.get(i).second);
S2CellId currentS2CellRangeStart = currentRange.rangeStart;
S2CellId currentS2CellRangeEnd = currentRange.rangeEnd;
if (rangeStart == null) {
// First time round the loop initialize rangeStart / rangeEnd only.
rangeStart = currentS2CellRangeStart;
- } else if (rangeEnd.id() != currentS2CellRangeStart.id()) {
- // If there's a gap between cellIds, store the range we have so far and start a
- // new range.
- ranges.add(new SatS2Range(rangeStart, rangeEnd));
+ rangeEntryValue = currentRange.entryValue;
+ } else if (rangeEnd.id() != currentS2CellRangeStart.id()
+ || currentRange.entryValue != rangeEntryValue) {
+ // If there's a gap between cellIds or entry values are different, store the
+ // range we have so far and start a new range.
+ ranges.add(new SatS2Range(rangeStart, rangeEnd, rangeEntryValue));
rangeStart = currentS2CellRangeStart;
+ rangeEntryValue = currentRange.entryValue;
}
rangeEnd = currentS2CellRangeEnd;
}
- ranges.add(new SatS2Range(rangeStart, rangeEnd));
+ ranges.add(new SatS2Range(rangeStart, rangeEnd, rangeEntryValue));
}
// Sorting the ranges is not necessary. As the input is sorted , it will already be sorted.
@@ -226,8 +258,7 @@
/**
* @return A pair of S2CellId for the range [s2CellId, s2CellId's next sibling)
*/
- private static SatS2Range createS2Range(
- S2CellId s2CellId, int s2Level) {
+ private static SatS2Range createS2Range(S2CellId s2CellId, int s2Level, int entryValue) {
// Since s2CellId is at s2Level, s2CellId.childBegin(s2Level) returns itself.
S2CellId firstS2CellRangeStart = s2CellId.childBegin(s2Level);
// Get the immediate next sibling of s2CellId
@@ -240,7 +271,7 @@
+ ", childEnd(" + s2Level + ") produced an unsupported"
+ " value=" + firstS2CellRangeEnd);
}
- return new SatS2Range(firstS2CellRangeStart, firstS2CellRangeEnd);
+ return new SatS2Range(firstS2CellRangeStart, firstS2CellRangeEnd, entryValue);
}
private static void checkCellIdIsAtLevel(S2CellId cellId, int s2Level) {
@@ -255,6 +286,7 @@
* (inclusive) and an end cell ID (exclusive).
*/
private static class SatS2Range {
+ public final int entryValue;
public final S2CellId rangeStart;
public final S2CellId rangeEnd;
@@ -262,7 +294,8 @@
* Creates an instance. If the range is invalid or the cell IDs are from different levels
* this method throws an {@link IllegalArgumentException}.
*/
- SatS2Range(S2CellId rangeStart, S2CellId rangeEnd) {
+ SatS2Range(S2CellId rangeStart, S2CellId rangeEnd, int entryValue) {
+ this.entryValue = entryValue;
this.rangeStart = Objects.requireNonNull(rangeStart);
this.rangeEnd = Objects.requireNonNull(rangeEnd);
if (rangeStart.level() != rangeEnd.level()) {
@@ -275,4 +308,17 @@
}
}
}
+
+ /** A basic pair class. */
+ static class Pair<A, B> {
+
+ public final A first;
+
+ public final B second;
+
+ Pair(A first, B second) {
+ this.first = first;
+ this.second = second;
+ }
+ }
}
diff --git a/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/SatS2LocationLookup.java b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/SatS2LocationLookup.java
index 713cca8..9a03d7c 100644
--- a/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/SatS2LocationLookup.java
+++ b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/SatS2LocationLookup.java
@@ -17,6 +17,7 @@
package com.android.telephony.tools.sats2;
import com.android.telephony.sats2range.read.SatS2RangeFileReader;
+import com.android.telephony.sats2range.read.SuffixTableRange;
import com.beust.jcommander.JCommander;
import com.beust.jcommander.Parameter;
@@ -43,10 +44,12 @@
satS2RangeFileReader.getS2Level());
System.out.println("s2CellId=" + Long.toUnsignedString(s2CellId.id())
+ ", token=" + s2CellId.toToken());
- if (satS2RangeFileReader.findEntryByCellId(s2CellId.id()) == null) {
+ SuffixTableRange entry = satS2RangeFileReader.findEntryByCellId(s2CellId.id());
+ if (entry == null) {
System.out.println("The input file does not contain the input location");
} else {
- System.out.println("The input file contains the input location");
+ System.out.println("The input file contains the input location, entryValue="
+ + entry.getEntryValue());
}
}
}
diff --git a/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/dump/SuffixTableBlockDumper.java b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/dump/SuffixTableBlockDumper.java
index a5d75b4..7e0246a 100644
--- a/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/dump/SuffixTableBlockDumper.java
+++ b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/dump/SuffixTableBlockDumper.java
@@ -55,11 +55,12 @@
writer.println("Entry count=" + entryCount);
if (entryCount > 0) {
for (int i = 0; i < entryCount; i++) {
- writer.println(
- "[" + i + "]=" + suffixTableBlock.getEntryByIndex(i)
- .getSuffixTableRange());
+ writer.println("Entry[" + i + "]=" + suffixTableBlock.getEntryByIndex(
+ i).getSuffixTableRange());
}
}
+ int entryValueCount = suffixTableBlock.getEntryValueCount();
+ writer.println("Entry value count=" + entryValueCount);
}
}
}
diff --git a/utils/satellite/tools/src/test/java/com/android/telephony/tools/sats2/CreateSatS2FileTest.java b/utils/satellite/tools/src/test/java/com/android/telephony/tools/sats2/CreateSatS2FileTest.java
index 80c1807..13ec22e 100644
--- a/utils/satellite/tools/src/test/java/com/android/telephony/tools/sats2/CreateSatS2FileTest.java
+++ b/utils/satellite/tools/src/test/java/com/android/telephony/tools/sats2/CreateSatS2FileTest.java
@@ -16,11 +16,14 @@
package com.android.telephony.tools.sats2;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.assertNull;
import static org.junit.Assert.fail;
import com.android.telephony.sats2range.read.SatS2RangeFileFormat;
import com.android.telephony.sats2range.read.SatS2RangeFileReader;
+import com.android.telephony.sats2range.read.SuffixTableRange;
import com.android.telephony.sats2range.utils.TestUtils;
import org.junit.After;
@@ -34,6 +37,10 @@
/** Tests for {@link CreateSatS2File} */
public final class CreateSatS2FileTest {
+ private static final int S2_LEVEL = 12;
+ private static final boolean IS_ALLOWED_LIST = true;
+ private static final int ENTRY_VALUE_BYTE_SIZE = 4;
+ private static final int VERSION_NUMBER = 0;
private Path mTempDirPath;
@Before
@@ -49,19 +56,7 @@
}
@Test
- public void testCreateSatS2FileWithValidInput_AllowedList() throws Exception {
- testCreateSatS2FileWithValidInput(true);
- }
-
- @Test
- public void testCreateSatS2FileWithValidInput_DisallowedList() throws Exception {
- testCreateSatS2FileWithValidInput(false);
- }
-
- @Test
public void testCreateSatS2FileWithInvalidInput() throws Exception {
- int s2Level = 12;
- boolean isAllowedList = true;
Path inputDirPath = mTempDirPath.resolve("input");
Files.createDirectory(inputDirPath);
Path inputFilePath = inputDirPath.resolve("s2cells.txt");
@@ -71,14 +66,17 @@
Path outputFilePath = outputDirPath.resolve("sats2.dat");
// Create test input S2 cell file
- SatS2RangeFileFormat fileFormat = FileFormats.getFileFormatForLevel(s2Level, isAllowedList);
+ SatS2RangeFileFormat fileFormat = FileFormats.getFileFormatForLevel(S2_LEVEL,
+ IS_ALLOWED_LIST, ENTRY_VALUE_BYTE_SIZE, VERSION_NUMBER);
TestUtils.createInvalidTestS2CellFile(inputFilePath.toFile(), fileFormat);
// Commandline input arguments
String[] args = {
"--input-file", inputFilePath.toAbsolutePath().toString(),
- "--s2-level", String.valueOf(s2Level),
- "--is-allowed-list", isAllowedList ? "true" : "false",
+ "--s2-level", String.valueOf(S2_LEVEL),
+ "--is-allowed-list", String.valueOf(IS_ALLOWED_LIST),
+ "--entry-value-byte-size", String.valueOf(ENTRY_VALUE_BYTE_SIZE),
+ "--version-number", String.valueOf(VERSION_NUMBER),
"--output-file", outputFilePath.toAbsolutePath().toString()
};
@@ -92,8 +90,8 @@
fail("Exception should have been caught");
}
- private void testCreateSatS2FileWithValidInput(boolean isAllowedList) throws Exception {
- int s2Level = 12;
+ @Test
+ public void testCreateSatS2FileWithValidInput() throws Exception {
Path inputDirPath = mTempDirPath.resolve("input");
Files.createDirectory(inputDirPath);
Path inputFilePath = inputDirPath.resolve("s2cells.txt");
@@ -104,18 +102,24 @@
/*
* Create test input S2 cell file with the following ranges:
- * 1) [(prefix=0b100_11111111, suffix=1000), (prefix=0b100_11111111, suffix=2000))
- * 2) [(prefix=0b100_11111111, suffix=2001), (prefix=0b100_11111111, suffix=3000))
- * 3) [(prefix=0b101_11111111, suffix=1000), (prefix=0b101_11111111, suffix=2001))
+ * 1) [(prefix=0b100_11111111, suffix=1000), (prefix=0b100_11111111, suffix=2000),
+ * entryValue=1)
+ * 2) [(prefix=0b100_11111111, suffix=2001), (prefix=0b100_11111111, suffix=3000),
+ * entryValue=2)
+ * 3) [(prefix=0b101_11111111, suffix=1000), (prefix=0b101_11111111, suffix=2001)),
+ * entryValue=3)
*/
- SatS2RangeFileFormat fileFormat = FileFormats.getFileFormatForLevel(s2Level, isAllowedList);
+ SatS2RangeFileFormat fileFormat = FileFormats.getFileFormatForLevel(S2_LEVEL,
+ IS_ALLOWED_LIST, ENTRY_VALUE_BYTE_SIZE, VERSION_NUMBER);
TestUtils.createValidTestS2CellFile(inputFilePath.toFile(), fileFormat);
// Commandline input arguments
String[] args = {
"--input-file", inputFilePath.toAbsolutePath().toString(),
- "--s2-level", String.valueOf(s2Level),
- "--is-allowed-list", isAllowedList ? "true" : "false",
+ "--s2-level", String.valueOf(S2_LEVEL),
+ "--is-allowed-list", String.valueOf(IS_ALLOWED_LIST),
+ "--entry-value-byte-size", String.valueOf(ENTRY_VALUE_BYTE_SIZE),
+ "--version-number", String.valueOf(VERSION_NUMBER),
"--output-file", outputFilePath.toAbsolutePath().toString()
};
@@ -130,11 +134,6 @@
try {
SatS2RangeFileReader satS2RangeFileReader =
SatS2RangeFileReader.open(outputFilePath.toFile());
- if (isAllowedList != satS2RangeFileReader.isAllowedList()) {
- fail("isAllowedList="
- + satS2RangeFileReader.isAllowedList() + " does not match the input "
- + "argument=" + isAllowedList);
- }
// Verify an edge cell (prefix=0b100_11111111, suffix=100)
long s2CellId = fileFormat.createCellId(0b100_11111111, 100);
@@ -144,6 +143,10 @@
s2CellId = fileFormat.createCellId(0b100_11111111, 2000);
assertNull(satS2RangeFileReader.findEntryByCellId(s2CellId));
+ // Verify a middle cell (prefix=0b100_11111111, suffix=2000)
+ s2CellId = fileFormat.createCellId(0b100_11111111, 2000);
+ assertNull(satS2RangeFileReader.findEntryByCellId(s2CellId));
+
// Verify an edge cell (prefix=0b100_11111111, suffix=4000)
s2CellId = fileFormat.createCellId(0b100_11111111, 4000);
assertNull(satS2RangeFileReader.findEntryByCellId(s2CellId));
@@ -163,4 +166,320 @@
fail("Unexpected exception when validating the output ex=" + ex);
}
}
+
+ @Test
+ public void testCreateSatS2FileWithValidCellIdAndValidEntryValue() throws Exception {
+ Path inputDirPath = mTempDirPath.resolve("input");
+ Files.createDirectory(inputDirPath);
+ Path inputFilePath = inputDirPath.resolve("s2cells.txt");
+
+ Path outputDirPath = mTempDirPath.resolve("output");
+ Files.createDirectory(outputDirPath);
+ Path outputFilePath = outputDirPath.resolve("sats2.dat");
+
+ /*
+ * Create test input S2 cell file with the following ranges:
+ * 1) [(prefix=0b100_11111111, suffix=1000), (prefix=0b100_11111111, suffix=1500),
+ * entryValue=1)
+ * 2) [(prefix=0b100_11111111, suffix=1500), (prefix=0b100_11111111, suffix=2000),
+ * entryValue=2)
+ * 3) [(prefix=0b100_11111111, suffix=2001), (prefix=0b100_11111111, suffix=3000),
+ * entryValue=3)
+ * 4) [(prefix=0b101_11111111, suffix=1000), (prefix=0b101_11111111, suffix=2001)),
+ * entryValue=4)
+ */
+ SatS2RangeFileFormat fileFormat = FileFormats.getFileFormatForLevel(S2_LEVEL,
+ IS_ALLOWED_LIST, ENTRY_VALUE_BYTE_SIZE, VERSION_NUMBER);
+ TestUtils.createValidTestS2CellFileWithValidEntryValue(inputFilePath.toFile(), fileFormat);
+
+ // Commandline input arguments
+ String[] args = {
+ "--input-file", inputFilePath.toAbsolutePath().toString(),
+ "--s2-level", String.valueOf(S2_LEVEL),
+ "--is-allowed-list", String.valueOf(IS_ALLOWED_LIST),
+ "--entry-value-byte-size", String.valueOf(ENTRY_VALUE_BYTE_SIZE),
+ "--version-number", String.valueOf(VERSION_NUMBER),
+ "--output-file", outputFilePath.toAbsolutePath().toString()
+ };
+
+ // Execute the tool CreateSatS2File and expect successful result
+ try {
+ CreateSatS2File.main(args);
+ } catch (Exception ex) {
+ fail("Unexpected exception when executing the tool ex=" + ex);
+ }
+
+
+ // Validate the output block file
+ try {
+ SatS2RangeFileReader satS2RangeFileReader =
+ SatS2RangeFileReader.open(outputFilePath.toFile());
+
+ // Verify a cell outside the valid range (prefix=0b100_11111111, suffix=0)
+ long s2CellId = fileFormat.createCellId(0b100_11111111, 0);
+ SuffixTableRange suffixTableRange = satS2RangeFileReader.findEntryByCellId(s2CellId);
+ assertNull(suffixTableRange);
+
+ // Verify a cell outside the valid range (prefix=0b100_11111111, suffix=0)
+ s2CellId = fileFormat.createCellId(0b100_11111111, 999);
+ suffixTableRange = satS2RangeFileReader.findEntryByCellId(s2CellId);
+ assertNull(suffixTableRange);
+
+ // Verify the first cell (prefix=0b100_11111111, suffix=1000)
+ int expectedEntryValue = 1;
+ s2CellId = fileFormat.createCellId(0b100_11111111, 1000);
+ suffixTableRange = satS2RangeFileReader.findEntryByCellId(s2CellId);
+ assertNotNull(suffixTableRange);
+ Integer entryValue = suffixTableRange.getEntryValue();
+ assertNotNull(entryValue);
+ assertEquals(expectedEntryValue, (int) entryValue);
+
+ // Verify the mid cell of 1st range (prefix=0b100_11111111, suffix=1499)
+ s2CellId = fileFormat.createCellId(0b100_11111111, 1250);
+ suffixTableRange = satS2RangeFileReader.findEntryByCellId(s2CellId);
+ assertNotNull(suffixTableRange);
+ entryValue = suffixTableRange.getEntryValue();
+ assertNotNull(entryValue);
+ assertEquals(expectedEntryValue, (int) entryValue);
+
+ // Verify the end of 1st range (prefix=0b100_11111111, suffix=1499)
+ s2CellId = fileFormat.createCellId(0b100_11111111, 1499);
+ suffixTableRange = satS2RangeFileReader.findEntryByCellId(s2CellId);
+ assertNotNull(suffixTableRange);
+ entryValue = suffixTableRange.getEntryValue();
+ assertNotNull(entryValue);
+ assertEquals(expectedEntryValue, (int) entryValue);
+
+ // Verify the first cell of 2nd range (prefix=0b100_11111111, suffix=1500)
+ expectedEntryValue = 2;
+ s2CellId = fileFormat.createCellId(0b100_11111111, 1500);
+ suffixTableRange = satS2RangeFileReader.findEntryByCellId(s2CellId);
+ assertNotNull(suffixTableRange);
+ entryValue = suffixTableRange.getEntryValue();
+ assertNotNull(entryValue);
+ assertEquals(expectedEntryValue, (int) entryValue);
+
+ // Verify the mid cell of 2nd range (prefix=0b100_11111111, suffix=1750)
+ s2CellId = fileFormat.createCellId(0b100_11111111, 1750);
+ suffixTableRange = satS2RangeFileReader.findEntryByCellId(s2CellId);
+ assertNotNull(suffixTableRange);
+ entryValue = suffixTableRange.getEntryValue();
+ assertNotNull(entryValue);
+ assertEquals(expectedEntryValue, (int) entryValue);
+
+ // Verify the end cell of 2nd range (prefix=0b100_11111111, suffix=1999)
+ s2CellId = fileFormat.createCellId(0b100_11111111, 1999);
+ suffixTableRange = satS2RangeFileReader.findEntryByCellId(s2CellId);
+ assertNotNull(suffixTableRange);
+ entryValue = suffixTableRange.getEntryValue();
+ assertNotNull(entryValue);
+ assertEquals(expectedEntryValue, (int) entryValue);
+
+ // Verify a cell outside the valid range (prefix=0b100_11111111, suffix=2000)
+ s2CellId = fileFormat.createCellId(0b100_11111111, 2000);
+ suffixTableRange = satS2RangeFileReader.findEntryByCellId(s2CellId);
+ assertNull(suffixTableRange);
+
+ expectedEntryValue = 3;
+ // Verify the first cell of 3rd range (prefix=0b100_11111111, suffix=2001)
+ s2CellId = fileFormat.createCellId(0b100_11111111, 2001);
+ suffixTableRange = satS2RangeFileReader.findEntryByCellId(s2CellId);
+ assertNotNull(suffixTableRange);
+ entryValue = suffixTableRange.getEntryValue();
+ assertNotNull(entryValue);
+ assertEquals(expectedEntryValue, (int) entryValue);
+
+ // Verify the mid cell of 3rd range (prefix=0b100_11111111, suffix=2001)
+ s2CellId = fileFormat.createCellId(0b100_11111111, 2500);
+ suffixTableRange = satS2RangeFileReader.findEntryByCellId(s2CellId);
+ assertNotNull(suffixTableRange);
+ entryValue = suffixTableRange.getEntryValue();
+ assertNotNull(entryValue);
+ assertEquals(expectedEntryValue, (int) entryValue);
+
+ // Verify the end cell of 3rd range (prefix=0b100_11111111, suffix=2999)
+ s2CellId = fileFormat.createCellId(0b100_11111111, 2999);
+ suffixTableRange = satS2RangeFileReader.findEntryByCellId(s2CellId);
+ assertNotNull(suffixTableRange);
+ entryValue = suffixTableRange.getEntryValue();
+ assertNotNull(entryValue);
+ assertEquals(expectedEntryValue, (int) entryValue);
+
+ // Verify a cell outside the valid range(prefix=0b100_11111111, suffix=3000)
+ s2CellId = fileFormat.createCellId(0b100_11111111, 3000);
+ suffixTableRange = satS2RangeFileReader.findEntryByCellId(s2CellId);
+ assertNull(suffixTableRange);
+
+ int maxSuffixValue = (1 << fileFormat.getSuffixBitCount()) - 1;
+ // Verify a cell outside the valid range (prefix=0b100_11111111, suffix=max value)
+ s2CellId = fileFormat.createCellId(0b100_11111111, maxSuffixValue);
+ suffixTableRange = satS2RangeFileReader.findEntryByCellId(s2CellId);
+ assertNull(suffixTableRange);
+
+ // Verify a cell outside the valid range (prefix=0b101_11111111, suffix=0)
+ s2CellId = fileFormat.createCellId(0b101_11111111, 0);
+ suffixTableRange = satS2RangeFileReader.findEntryByCellId(s2CellId);
+ assertNull(suffixTableRange);
+
+ // Verify a cell outside the valid range (prefix=0b101_11111111, suffix=999)
+ s2CellId = fileFormat.createCellId(0b101_11111111, 999);
+ suffixTableRange = satS2RangeFileReader.findEntryByCellId(s2CellId);
+ assertNull(suffixTableRange);
+
+ // Verify the first cell of 4th range (prefix=0b101_11111111, suffix=1000)
+ expectedEntryValue = 4;
+ s2CellId = fileFormat.createCellId(0b101_11111111, 1000);
+ suffixTableRange = satS2RangeFileReader.findEntryByCellId(s2CellId);
+ assertNotNull(suffixTableRange);
+ entryValue = suffixTableRange.getEntryValue();
+ assertNotNull(entryValue);
+ assertEquals(expectedEntryValue, (int) entryValue);
+
+ // Verify a mid cell of 4th range (prefix=0b101_11111111, suffix=1500)
+ s2CellId = fileFormat.createCellId(0b101_11111111, 1500);
+ suffixTableRange = satS2RangeFileReader.findEntryByCellId(s2CellId);
+ assertNotNull(suffixTableRange);
+ entryValue = suffixTableRange.getEntryValue();
+ assertNotNull(entryValue);
+ assertEquals(expectedEntryValue, (int) entryValue);
+
+ // Verify a cell of 4th range (prefix=0b101_11111111, suffix=2000)
+ s2CellId = fileFormat.createCellId(0b101_11111111, 2000);
+ suffixTableRange = satS2RangeFileReader.findEntryByCellId(s2CellId);
+ assertNotNull(suffixTableRange);
+ entryValue = suffixTableRange.getEntryValue();
+ assertNotNull(entryValue);
+ assertEquals(expectedEntryValue, (int) entryValue);
+
+ // Verify the end cell of 4th range (prefix=0b101_11111111, suffix=2001)
+ s2CellId = fileFormat.createCellId(0b101_11111111, 2001);
+ suffixTableRange = satS2RangeFileReader.findEntryByCellId(s2CellId);
+ assertNull(suffixTableRange);
+
+ // Verify a cell outside the valid range (prefix=0b101_11111111, suffix=max value)
+ s2CellId = fileFormat.createCellId(0b101_11111111, maxSuffixValue);
+ suffixTableRange = satS2RangeFileReader.findEntryByCellId(s2CellId);
+ assertNull(suffixTableRange);
+ } catch (Exception ex) {
+ fail("Unexpected exception when validating the output ex=" + ex);
+ }
+ }
+
+ @Test
+ public void testCreateSatS2FileWithValidInputAndRandomEntryValue() throws Exception {
+ String inputFileName = "s2cells_random_entry_value.txt";
+ Path inputDirPath = mTempDirPath.resolve("input");
+ Path inputFilePath = inputDirPath.resolve(inputFileName);
+ TestUtils.copyTestResource(getClass(), inputFileName, inputDirPath);
+
+ Path outputDirPath = mTempDirPath.resolve("output");
+ Files.createDirectory(outputDirPath);
+ Path outputFilePath = outputDirPath.resolve("sats2.dat");
+
+ // Commandline input arguments
+ String[] args = {
+ "--input-file", inputFilePath.toAbsolutePath().toString(),
+ "--s2-level", String.valueOf(S2_LEVEL),
+ "--is-allowed-list", String.valueOf(IS_ALLOWED_LIST),
+ "--entry-value-byte-size", String.valueOf(ENTRY_VALUE_BYTE_SIZE),
+ "--version-number", String.valueOf(VERSION_NUMBER),
+ "--output-file", outputFilePath.toAbsolutePath().toString()
+ };
+
+ // Execute the tool CreateSatS2File and expect successful result
+ try {
+ CreateSatS2File.main(args);
+ } catch (Exception ex) {
+ fail("Unexpected exception when executing the tool ex=" + ex);
+ }
+ }
+
+ @Test
+ public void testCreateSatS2FileWithValidCellIdAndInValidInputParameter() throws Exception {
+ Path inputDirPath = mTempDirPath.resolve("input");
+ Files.createDirectory(inputDirPath);
+ Path inputFilePath = inputDirPath.resolve("s2cells.txt");
+
+ Path outputDirPath = mTempDirPath.resolve("output");
+ Files.createDirectory(outputDirPath);
+ Path outputFilePath = outputDirPath.resolve("sats2.dat");
+
+ /*
+ * Create test input S2 cell file with the following ranges:
+ * 1) [(prefix=0b100_11111111, suffix=1000), (prefix=0b100_11111111, suffix=1500),
+ * entryValue=1)
+ * 2) [(prefix=0b100_11111111, suffix=1500), (prefix=0b100_11111111, suffix=2000),
+ * entryValue=2)
+ * 3) [(prefix=0b100_11111111, suffix=2001), (prefix=0b100_11111111, suffix=3000),
+ * entryValue=3)
+ * 4) [(prefix=0b101_11111111, suffix=1000), (prefix=0b101_11111111, suffix=2001)),
+ * entryValue=4)
+ */
+ SatS2RangeFileFormat fileFormat = FileFormats.getFileFormatForLevel(S2_LEVEL,
+ IS_ALLOWED_LIST, ENTRY_VALUE_BYTE_SIZE, VERSION_NUMBER);
+ TestUtils.createValidTestS2CellFileWithValidEntryValue(inputFilePath.toFile(), fileFormat);
+
+ // Entry value size in byte < 0
+ String[] args = {
+ "--input-file", inputFilePath.toAbsolutePath().toString(),
+ "--s2-level", String.valueOf(S2_LEVEL),
+ "--is-allowed-list", String.valueOf(IS_ALLOWED_LIST),
+ "--entry-value-byte-size", String.valueOf(-1),
+ "--version-number", String.valueOf(VERSION_NUMBER),
+ "--output-file", outputFilePath.toAbsolutePath().toString()
+ };
+
+ // Execute the tool CreateSatS2File and expect exception
+ try {
+ CreateSatS2File.main(args);
+ fail("Exception should have been caught");
+ } catch (IllegalArgumentException ex) {
+ // Expected exception
+ } catch (Exception ex) {
+ // Unexpected exception
+ fail("Unexpected exception, ex=" + ex);
+ }
+
+ // isAllowList is false && entryValueSizeInBytes > 0
+ args = new String[]{
+ "--input-file", inputFilePath.toAbsolutePath().toString(),
+ "--s2-level", String.valueOf(S2_LEVEL),
+ "--is-allowed-list", String.valueOf(false),
+ "--entry-value-byte-size", String.valueOf(ENTRY_VALUE_BYTE_SIZE),
+ "--version-number", String.valueOf(VERSION_NUMBER),
+ "--output-file", outputFilePath.toAbsolutePath().toString()
+ };
+
+ // Execute the tool CreateSatS2File and expect exception
+ try {
+ CreateSatS2File.main(args);
+ fail("Exception should have been caught");
+ } catch (IllegalArgumentException ex) {
+ // Expected exception
+ } catch (Exception ex) {
+ // Unexpected exception
+ fail("Unexpected exception, ex=" + ex);
+ }
+
+ // entryValueSizeInBytes > 4
+ args = new String[]{
+ "--input-file", inputFilePath.toAbsolutePath().toString(),
+ "--s2-level", String.valueOf(S2_LEVEL),
+ "--is-allowed-list", String.valueOf(IS_ALLOWED_LIST),
+ "--entry-value-byte-size", String.valueOf(ENTRY_VALUE_BYTE_SIZE + 1),
+ "--version-number", String.valueOf(VERSION_NUMBER),
+ "--output-file", outputFilePath.toAbsolutePath().toString()
+ };
+
+ // Execute the tool CreateSatS2File and expect exception
+ try {
+ CreateSatS2File.main(args);
+ fail("Exception should have been caught");
+ } catch (IllegalArgumentException ex) {
+ // Expected exception
+ } catch (Exception ex) {
+ // Unexpected exception
+ fail("Unexpected exception, ex=" + ex);
+ }
+ }
}
diff --git a/utils/satellite/tools/src/test/java/com/android/telephony/tools/sats2/data/s2cells_random_entry_value.txt b/utils/satellite/tools/src/test/java/com/android/telephony/tools/sats2/data/s2cells_random_entry_value.txt
new file mode 100644
index 0000000..24ca950
--- /dev/null
+++ b/utils/satellite/tools/src/test/java/com/android/telephony/tools/sats2/data/s2cells_random_entry_value.txt
@@ -0,0 +1,1545 @@
+5522342230481698816,3
+5522349927063093248,9
+5522732557109559296,2
+5522767741481648128,3
+5522789731714203648,4
+5522798527807225856,2
+5522890886783959040,6
+5522978847714181120,0
+5523000837946736640,9
+5523027226225803264,8
+5523081102295564288,2
+5523088798876958720,2
+5523097594969980928,3
+5523103092528119808,0
+5523827670690824192,3
+5523858457016401920,5
+5523893641388490752,3
+5523915631621046272,4
+5523924427714068480,2
+5523977204272201728,9
+5523999194504757248,1
+5524021184737312768,7
+5524029980830334976,5
+5524038776923357184,5
+5524789743365128192,2
+5524808435062800384,4
+5524843619434889216,4
+5524878803806978048,8
+5524909590132555776,6
+5525067919806955520,2
+5525089910039511040,3
+5525138288551133184,5
+5525160278783688704,7
+5525195463155777536,0
+5525283424085999616,0
+5525635267806887936,2
+5526198217760309248,1
+5526761167713730560,7
+5527324117667151872,5
+5527609990690373632,2
+5527618786783395840,3
+5527627582876418048,6
+5527634918680559616,0
+5527728737946173440,2
+5527763922318262272,6
+5527799106690351104,9
+5527834291062439936,0
+5527856281294995456,1
+5527865077388017664,5
+5527921152481034240,9
+5527926650039173120,3
+5527935446132195328,3
+5527944242225217536,9
+5527970630504284160,2
+5527978327085678592,4
+5528542376550727680,0
+5528551172643749888,3
+5528559968736772096,5
+5528586357015838720,2
+5528595153108860928,5
+5528603949201883136,8
+5528718298411171840,5
+5529012967527415808,5
+5529312034690170880,9
+5529334024922726400,1
+5529342821015748608,1
+5529348318573887488,7
+5529360413201793024,4
+5529382403434348544,3
+5529417587806437376,9
+5529505548736659456,3
+5529580315527348224,1
+5529606703806414848,8
+5529765033480814592,5
+5529809013945925632,8
+5529998061226426368,0
+5530002527992414208,8
+5530028916271480832,8
+5530037712364503040,1
+5530046508457525248,9
+5533098752736231424,1
+5533107548829253632,4
+5533221898038542336,1
+5533230694131564544,9
+5533516567154786304,8
+5533805738712891392,2
+5533811236271030272,0
+5533820032364052480,5
+5533859546063175680,6
+5533864012829163520,5
+5533886003061719040,3
+5533921187433807872,2
+5534009148364029952,0
+5534083915154718720,1
+5534096009782624256,9
+5534101507340763136,1
+5534110303433785344,2
+5534132293666340864,5
+5534157582433779712,7
+5534163079991918592,0
+5534170776573313024,2
+5534268633108185088,6
+5562600848732717056,8
+5562605315498704896,9
+5562672316988522496,3
+5562699066044841984,5
+5562706401848983552,1
+5562715197942005760,4
+5562737188174561280,1
+5562772372546650112,7
+5562860333476872192,9
+5562948294407094272,1
+5562970284639649792,9
+5562979080732672000,3
+5562996672918716416,6
+5563059619959406592,8
+5563352914686115840,9
+5563651981848870912,4
+5563673972081426432,1
+5563700360360493056,9
+5563709156453515264,8
+5563717952546537472,1
+5563737009316429824,3
+5563757534965137408,8
+5563779525197692928,6
+5563805913476759552,2
+5563814709569781760,1
+5563819382494199808,3
+5567879947655053312,1
+5567913688918130688,7
+5567922485011152896,5
+5567944475243708416,0
+5567979659615797248,9
+5568001649848352768,1
+5568010445941374976,2
+5568028038127419392,7
+5568124795150663680,2
+5568129261916651520,2
+5568758113848262656,0
+5568763611406401536,1
+5568788900173840384,9
+5568806767237791744,1
+5568854870871506944,8
+5568863666964529152,3
+5568894453290106880,8
+5568929637662195712,0
+5568964822034284544,1
+5569052782964506624,0
+5569193520452861952,0
+5569545364173750272,2
+5570108314127171584,9
+5570671264080592896,6
+5572078638964146176,6
+5573274907615166464,4
+5573499207987232768,4
+5573594865498849280,0
+5573613557196521472,6
+5573622353289543680,0
+5573697120080232448,7
+5573837857568587776,9
+5573978595056943104,3
+5574053361847631872,5
+5574081124516233216,4
+5574238079801098240,9
+5574246875894120448,0
+5574255671987142656,2
+5574277662219698176,2
+5806560488703655936,7
+5806567910407143424,6
+5806635255494344704,3
+5806670439866433536,5
+5806705624238522368,1
+5806727614471077888,4
+5806754002750144512,7
+5806775992982700032,8
+5806811177354788864,6
+5806846361726877696,3
+5806868351959433216,0
+5806885944145477632,2
+5806894740238499840,9
+5806916730471055360,3
+5806951914843144192,6
+5806982701168721920,7
+5807097050378010624,1
+5807105846471032832,6
+5815321397353775104,1
+5815330193446797312,4
+5815355482214236160,1
+5815572086004908032,4
+5815592701847928832,7
+5815611668423507968,6
+5815620464516530176,3
+5815642454749085696,3
+5815677639121174528,9
+5815765600051396608,0
+5815906337539751936,2
+5815981104330440704,3
+5815989900423462912,9
+5815997597004857344,2
+5816099851586240512,2
+5816135035958329344,9
+5816183414469951488,5
+5816192210562973696,9
+5816218598842040320,2
+5816240589074595840,2
+5816328550004817920,5
+5816469287493173248,2
+5816610024981528576,5
+5816750762469883904,3
+5816838723400105984,6
+5816873907772194816,3
+5816909092144283648,0
+5816931082376839168,0
+5816939878469861376,7
+5816948674562883584,0
+5817485236237238272,6
+5817494032330260480,4
+5817520420609327104,9
+5817529216702349312,8
+5817546808888393728,0
+5817555604981415936,8
+5817577595213971456,7
+5817960225260437504,6
+5817969021353459712,5
+5818013001818570752,3
+5818034992051126272,4
+5818070176423215104,2
+5818369243585970176,8
+5818721087306858496,6
+5818861824795213824,1
+5819002562283569152,4
+5819090523213791232,2
+5819125707585880064,5
+5819160891957968896,2
+5819182882190524416,7
+5819191678283546624,7
+5819200474376568832,4
+5819207804543565824,9
+5819235658748657664,4
+5819244454841679872,0
+5819266445074235392,1
+5819301629446324224,4
+5819331041382367232,0
+5819442366934679552,6
+5819477551306768384,7
+5819565512236990464,9
+5819706249725345792,8
+5820058093446234112,7
+5820621043399655424,4
+5822028418283208704,7
+5824280218096893952,5
+5825687592980447232,8
+5826250542933868544,9
+5826602386654756864,3
+5826743124143112192,9
+5826831085073334272,5
+5826866269445423104,8
+5826883862705209344,8
+5826932240143089664,3
+5826941036236111872,6
+5826976220608200704,5
+5826985016701222912,1
+5827007006933778432,3
+5827042191305867264,9
+5827064181538422784,1
+5827072977631444992,9
+5827090569817489408,1
+5827376442840711168,7
+5827662315863932928,4
+5827671111956955136,6
+5827785461166243840,3
+5827790134090661888,3
+5830617803119394816,2
+5830644191398461440,9
+5830652987491483648,8
+5830661783584505856,8
+5830670579677528064,7
+5843438108699262976,9
+5843490610379489280,1
+5843508477443440640,6
+5843543661815529472,1
+5843631622745751552,0
+5845414205972283392,6
+5845448015954837504,1
+5845456812047859712,9
+5845478802280415232,7
+5845513986652504064,0
+5845549171024592896,5
+5845659122187370496,7
+5845667918280392704,0
+5846798216233746432,5
+5849050016047431680,7
+5850457390930984960,9
+5851020340884406272,1
+5851583290837827584,1
+5851935134558715904,3
+5852075872047071232,7
+5852216609535426560,1
+5852304570465648640,6
+5852339754837737472,9
+5852374939209826304,8
+5852401052610985984,6
+5852405725535404032,9
+5852413422116798464,9
+5852467298186559488,1
+5852476094279581696,3
+5852484890372603904,6
+5852720941775192064,2
+5852813644349308928,2
+5852832336046981120,7
+5852867520419069952,5
+5852889510651625472,1
+5852907102837669888,0
+5852915898930692096,9
+5852937889163247616,1
+5852973073535336448,0
+5853272140698091520,8
+5853566809814335488,5
+5853650303978569728,9
+5853654770744557568,3
+5853676760977113088,1
+5853764721907335168,7
+5853838389186396160,1
+5853860379418951680,8
+5853865876977090560,6
+5853887867209646080,9
+5853909857442201600,8
+5853918653535223808,2
+5853927449628246016,0
+5856975291565473792,6
+5856979693906952192,3
+5857352428348768256,8
+5857371120046440448,8
+5857419498558062592,7
+5857441488790618112,8
+5857476673162706944,1
+5857564634092929024,6
+5857705371581284352,9
+5857846109069639680,5
+5857920875860328448,9
+5857938468046372864,0
+5857947264139395072,5
+5857969254371950592,4
+5858004438744039424,6
+5858033759143591936,9
+5858202350837039104,3
+5858223241557966848,3
+5858228739116105728,1
+5858250729348661248,8
+5858276018116100096,8
+5858281515674238976,0
+5858288937377726464,5
+5860648764208840704,1
+5860674052976279552,5
+5860682849069301760,4
+5954941781895282688,2
+5954968170174349312,0
+5954976966267371520,0
+5954985762360393728,9
+5955073723290615808,8
+5955082519383638016,0
+5955091315476660224,0
+5955113305709215744,0
+5955148490081304576,9
+5955236451011526656,0
+5955377188499881984,8
+5955517925988237312,3
+5955592692778926080,9
+5955601488871948288,6
+5955699706184073216,6
+5955710340523098112,5
+5955715838081236992,5
+5955724634174259200,1
+5955733430267281408,4
+5955742226360303616,4
+5955856575569592320,1
+5955865371662614528,8
+5955940138453303296,1
+5957136407104323584,5
+5959388206918008832,3
+5960795581801562112,5
+5961358531754983424,8
+5961644404778205184,6
+5962295315661848576,2
+5962304111754870784,7
+5962392072685092864,9
+5962400868778115072,3
+5962431655103692800,6
+5962466839475781632,9
+5962488829708337152,6
+5962506421894381568,4
+5962515217987403776,9
+5962537208219959296,4
+5962572392592048128,4
+5962594382824603648,8
+5962603178917625856,1
+5962673547661803520,6
+5962928634359447552,2
+5962937430452469760,0
+5962959420685025280,0
+5962994605057114112,6
+5963016595289669632,0
+5963025391382691840,3
+5963060575754780672,8
+5963069371847802880,5
+5963078167940825088,5
+5963100158173380608,6
+5963135342545469440,0
+5963170526917558272,6
+5963680700312846336,7
+5963821437801201664,5
+5964173281522089984,2
+5964736231475511296,4
+5966143606359064576,3
+5968395406172749824,7
+5969802781056303104,7
+5970365731009724416,6
+5970717574730612736,5
+5970858312218968064,2
+5970933079009656832,3
+5970959467288723456,9
+5970968263381745664,9
+5970973760939884544,5
+5971117796963123200,9
+5971126593056145408,1
+5971152981335212032,5
+5971161777428234240,2
+5971298116870078464,7
+5971320107102633984,9
+5971328903195656192,5
+5971346495381700608,7
+5971421262172389376,1
+5971561999660744704,6
+5971649960590966784,9
+5971685144963055616,8
+5986642901147320320,5
+5986651697240342528,6
+5986761648403120128,2
+5986849609333342208,7
+5986884793705431040,1
+5986906783937986560,5
+5986933172217053184,0
+5986955162449608704,8
+5986990346821697536,3
+5987025531193786368,3
+5987091501891452928,7
+5987100297984475136,9
+5987482928030941184,0
+5987504918263496704,1
+5987510415821635584,7
+5987531306542563328,8
+5987540102635585536,4
+5987548898728607744,7
+5987663247937896448,0
+5987668745496035328,9
+5989801798053920768,4
+5989809494635315200,1
+5989844679007404032,7
+5989853475100426240,2
+5989875465332981760,2
+5989910649705070592,9
+5989998610635292672,3
+5990139348123648000,0
+5990227309053870080,6
+5990262493425958912,9
+5990284483658514432,8
+5990293279751536640,6
+5990321132614451200,4
+5990328464123625472,2
+5990337260216647680,5
+5990346056309669888,9
+5990631929332891648,2
+5991194879286312960,4
+5991757829239734272,7
+5993165204123287552,7
+5995417003936972800,1
+5997668803750658048,8
+6003298303284871168,4
+6008083377888952320,3
+6008435221609840640,6
+6008523182540062720,7
+6008558366912151552,4
+6008580357144707072,4
+6008606745423773696,2
+6008628735656329216,1
+6008663920028418048,8
+6008766174609801216,8
+6008773871191195648,3
+6008782667284217856,7
+6008857434074906624,5
+6008945395005128704,1
+6008980579377217536,0
+6009002569609773056,4
+6009011365702795264,7
+6009016863260934144,9
+6009028957888839680,6
+6009050948121395200,2
+6009072938353950720,6
+6009373379906240512,8
+6009407189888794624,7
+6009415985981816832,0
+6009437976214372352,5
+6009473160586461184,8
+6009772227749216256,5
+6010124071470104576,2
+6010264808958459904,6
+6010352769888681984,0
+6010387954260770816,7
+6010409944493326336,1
+6010418740586348544,6
+6010423207352336384,7
+6010436332772392960,1
+6010458323004948480,9
+6010546283935170560,7
+6010687021423525888,0
+6010827758911881216,6
+6010915719842103296,5
+6010937710074658816,7
+6010946506167681024,6
+6011061954888597504,3
+6011091641702547456,0
+6011126826074636288,8
+6011148816307191808,8
+6011157612400214016,2
+6012072406074523648,0
+6012081202167545856,3
+6012111988493123584,5
+6052908267930124288,7
+6052991830813835264,0
+6053000626906857472,1
+6053035811278946304,1
+6053044607371968512,1
+6053066597604524032,8
+6053101781976612864,0
+6053189742906834944,6
+6053330480395190272,7
+6053471217883545600,5
+6053545984674234368,3
+6053554780767256576,4
+6053669129976545280,6
+6053677926069567488,8
+6053686722162589696,6
+6053695518255611904,3
+6053805469418389504,0
+6053893430348611584,1
+6054034167836966912,5
+6054122128767188992,3
+6054173805813694464,8
+6054179303371833344,5
+6054205691650899968,5
+6054227681883455488,1
+6054315642813677568,0
+6054456380302032896,3
+6054597117790388224,0
+6054737855278743552,5
+6054825816208965632,8
+6054861000581054464,5
+6054891786906632192,8
+6054997340022898688,7
+6055006136115920896,4
+6055032524394987520,6
+6055234834534498304,2
+6055252426720542720,9
+6055261222813564928,7
+6055283213046120448,8
+6055318397418209280,2
+6055340387650764800,9
+6055349183743787008,2
+6055384368115875840,2
+6055393164208898048,1
+6055401960301920256,6
+6055423950534475776,5
+6055459134906564608,7
+6055494319278653440,6
+6056070463371608064,1
+6056092453604163584,1
+6056144955284389888,0
+6056162822348341248,1
+6056198006720430080,0
+6056285967650652160,9
+6056360734441340928,3
+6056369530534363136,3
+6056378326627385344,2
+6056385679611396096,9
+6056479481697140736,9
+6056501471929696256,9
+6056510268022718464,7
+6056528959720390656,9
+6056643308929679360,6
+6056651005511073792,2
+6056659801604096000,9
+6056668597697118208,1
+6056690587929673728,1
+6056725772301762560,1
+6056760956673851392,7
+6057060023836606464,6
+6057345896859828224,7
+6057366787580755968,6
+6057372285138894848,4
+6057394275371450368,7
+6057768109324894208,8
+6057776905417916416,1
+6057785701510938624,6
+6057820885883027456,3
+6057829681976049664,3
+6057851672208605184,2
+6057886856580694016,6
+6057922040952782848,9
+6057944031185338368,3
+6057952827278360576,6
+6057970419464404992,1
+6058031992115560448,7
+6060345364580401152,4
+6089619861669937152,5
+6089627558251331584,3
+6089646249949003776,1
+6089653946530398208,6
+6089662742623420416,2
+6089671538716442624,7
+6089733111367598080,1
+6089737784292016128,3
+6089763897693175808,5
+6089799082065264640,1
+6089821072297820160,7
+6089829868390842368,6
+6089834541315260416,1
+6089847460576886784,4
+6090068462414069760,5
+6090076158995464192,3
+6090084955088486400,7
+6090093751181508608,8
+6090102547274530816,0
+6090130309943132160,8
+6090203702344286208,0
+6090344439832641536,9
+6090432400762863616,1
+6090467585134952448,6
+6090489575367507968,2
+6090498371460530176,0
+6090537953879130112,0
+6092283978344038400,7
+6092292774437060608,7
+6092679802530037760,7
+6092741375181193216,0
+6092754294442819584,3
+6092758967367237632,7
+6092767763460259840,6
+6092789753692815360,2
+6092877714623037440,5
+6092965675553259520,4
+6093000859925348352,9
+6093022850157903872,9
+6093031646250926080,0
+6093071228669526016,1
+6093089920367198208,7
+6093198772018348032,6
+6093219662739275776,5
+6093225160297414656,5
+6093299927088103424,2
+6093651770808991744,9
+6093950837971746816,2
+6093986022343835648,3
+6094021206715924480,7
+6094043196948480000,4
+6094051993041502208,7
+6094060789134524416,6
+6094205924602281984,0
+6094210322715901952,4
+6094232312948457472,6
+6094285020787113984,7
+6094289487553101824,5
+6094307079739146240,4
+6094315875832168448,3
+6094337866064723968,1
+6094425826994946048,1
+6094777670715834368,5
+6095340620669255680,2
+6096747995552808960,9
+6102377495087022080,8
+6107162569691103232,3
+6107483627086413824,6
+6107492423179436032,1
+6107501219272458240,4
+6107830797882884096,3
+6107835470807302144,3
+6107848596227358720,8
+6107853062993346560,7
+6107861859086368768,0
+6107883849318924288,7
+6107905839551479808,1
+6107923431737524224,0
+6107932227830546432,1
+6107954218063101952,6
+6107989402435190784,4
+6108077363365412864,7
+6108165324295634944,5
+6108187314528190464,2
+6108199409156096000,3
+6108204906714234880,0
+6108213702807257088,1
+6108235693039812608,7
+6108270877411901440,4
+6108358838342123520,4
+6108499575830478848,7
+6108851419551367168,4
+6110258794434920448,0
+6111455063085940736,9
+6111538625969651712,6
+6111635382992896000,6
+6111647477620801536,5
+6111652975178940416,3
+6111661771271962624,6
+6111683761504518144,3
+6111705751737073664,9
+6111723343923118080,9
+6111732140016140288,1
+6111754130248695808,8
+6111789314620784640,5
+6111877275551006720,0
+6112229119271895040,9
+6112580962992783360,5
+6112721700481138688,1
+6112809661411360768,5
+6112844845783449600,5
+6112972389132271616,1
+6112981185225293824,3
+6112989981318316032,4
+6113014995207847936,8
+6113249448882601984,0
+6113253864108982272,8
+6113262660202004480,7
+6113271456295026688,5
+6114344579643736064,9
+6114362171829780480,1
+6114370967922802688,5
+6114392958155358208,3
+6114428142527447040,9
+6114458928853024768,5
+6114523800039063552,2
+6114529297597202432,5
+6114538093690224640,4
+6118714863486238720,7
+6118804198805995520,5
+6118812994899017728,9
+6118825089526923264,5
+6118830587085062144,3
+6118839383178084352,4
+6118914149968773120,6
+6119015305038528512,9
+6119037295271084032,9
+6119063614830673920,8
+6119068081596661760,5
+6119075778178056192,2
+6219844919352098816,0
+6220231947445075968,7
+6220262733770653696,4
+6220284724003209216,1
+6220293520096231424,8
+6220311112282275840,0
+6220385879072964608,8
+6220473840003186688,9
+6220495830235742208,2
+6220504626328764416,6
+6220522218514808832,4
+6220526891439226880,5
+6220579393119453184,1
+6220878460282208256,0
+6221230304003096576,4
+6221318264933318656,4
+6221353449305407488,1
+6221375439537963008,1
+6221423818049585152,9
+6221445808282140672,6
+6221450481206558720,9
+6221473661145055232,3
+6221596441375145984,0
+6221604137956540416,3
+6221609635514679296,2
+6221634924282118144,4
+6221670108654206976,2
+6221705293026295808,7
+6221727283258851328,1
+6221732780816990208,3
+6221754771049545728,6
+6236726064970727424,3
+6236733417954738176,3
+6238237549861535744,3
+6238246345954557952,2
+6238272734233624576,6
+6238281530326646784,9
+6238286203251064832,2
+6238382685396402176,7
+6238417869768491008,0
+6238804897861468160,7
+6238840082233556992,8
+6238862072466112512,9
+6238866745390530560,9
+6238914849024245760,2
+6238923645117267968,2
+6238945635349823488,8
+6238980819721912320,6
+6239002809954467840,2
+6239011606047490048,1
+6244592727070081024,3
+6244733464558436352,5
+6244821425488658432,1
+6244856609860747264,3
+6244878600093302784,9
+6244886296674697216,3
+6244906087883997184,3
+6244926978604924928,6
+6244962162977013760,1
+6244997347349102592,4
+6245019337581658112,5
+6245028133674680320,8
+6245047186149605376,8
+6245058918926516224,8
+6245063318046769152,8
+6245072114139791360,2
+6245239239907213312,6
+6245248036000235520,9
+6245283220372324352,1
+6245292016465346560,2
+6245314006697902080,3
+6245349191069990912,2
+6245437152000212992,5
+6245643860186234880,9
+6245648259306487808,2
+6245801090349006848,9
+6245837374232723456,8
+6245846170325745664,7
+6245854966418767872,5
+6245876956651323392,0
+6245912141023412224,0
+6246000101953634304,2
+6246140839441989632,0
+6246215606232678400,8
+6246241994511745024,9
+6246250790604767232,1
+6246259586697789440,2
+6246400324186144768,0
+6246409120279166976,2
+6246435508558233600,9
+6246444304651255808,0
+6246453100744278016,4
+6246458598302416896,6
+6246774158139588608,1
+6247126001860476928,5
+6247209564744187904,8
+6247297525674409984,6
+6247319515906965504,4
+6247407476837187584,4
+6247548214325542912,4
+6247900058046431232,9
+6248463007999852544,8
+6248814851720740864,6
+6248955589209096192,9
+6249043550139318272,7
+6249065540371873792,8
+6249074336464896000,2
+6249153501302095872,1
+6249162297395118080,6
+6249237064185806848,3
+6249325025116028928,9
+6249360209488117760,4
+6249382199720673280,6
+6249390995813695488,1
+6249408587999739904,5
+6249430578232295424,7
+6249465762604384256,1
+6249487752836939776,2
+6249515240627634176,7
+6249568017185767424,9
+6249575713767161856,5
+6249823103883411456,4
+6250666429301915648,6
+6250785176557715456,0
+6250873137487937536,2
+6250908321860026368,9
+6250930312092581888,2
+6250935809650720768,6
+6250956700371648512,4
+6250978690604204032,8
+6255499882417618944,3
+6261129381951832064,5
+6263381181765517312,7
+6264788556649070592,3
+6265140400369958912,4
+6265228361300180992,4
+6265263545672269824,2
+6265285535904825344,5
+6265290208829243392,5
+6265313298573426688,3
+6265333914416447488,4
+6265355904649003008,5
+6265361402207141888,5
+6265383392439697408,5
+6265506537742008320,1
+6265514234323402752,9
+6265519731881541632,3
+6265545020648980480,4
+6265580205021069312,7
+6265615389393158144,4
+6265637379625713664,2
+6265642877183852544,1
+6265664867416408064,3
+6266280593927962624,7
+6266288290509357056,1
+6266293788067495936,3
+6266350962672140288,5
+6266358659253534720,8
+6266364156811673600,9
+6266389445579112448,3
+6266424629951201280,0
+6266459814323290112,3
+6266547775253512192,3
+6266635736183734272,0
+6266670920555823104,9
+6266692910788378624,9
+6266698408346517504,1
+6266720398579073024,1
+6266741289300000768,1
+6267884781392887808,1
+6273514280927100928,2
+6282521480181841920,3
+6287306554785923072,5
+6287869504739344384,5
+6288221348460232704,9
+6288309309390454784,4
+6288331299623010304,0
+6288335972547428352,2
+6288359062291611648,3
+6288411838849744896,0
+6288419260553232384,4
+6288423933477650432,5
+6288622945082277888,5
+6288630366785765376,7
+6288635039710183424,3
+6288661153111343104,6
+6288683143343898624,9
+6288687816268316672,1
+6288710631134593024,2
+6288995404646187008,4
+6289347248367075328,5
+6289435209297297408,2
+6289457199529852928,2
+6289462697087991808,4
+6289483587808919552,3
+6289536364367052800,3
+6289545160460075008,2
+6289553956553097216,4
+6289722181832146944,1
+6289751868646096896,8
+6289787053018185728,6
+6289822237390274560,5
+6289844227622830080,8
+6289853023715852288,6
+6289962974878629888,4
+6289998159250718720,5
+6290033343622807552,6
+6290055333855363072,6
+6290064129948385280,1
+6290097848662884352,7
+6295096869546622976,5
+6295104291250110464,4
+6295109788808249344,4
+6295135077575688192,8
+6295157067808243712,8
+6295162565366382592,6
+6295184555598938112,8
+6295258222877999104,2
+6295346183808221184,9
+6295368174040776704,5
+6295376970133798912,4
+6295394562319843328,5
+6295447338877976576,2
+6295456134970998784,5
+6295464931064020992,5
+6296124638040686592,8
+6296196381174398976,7
+6296225793110441984,9
+6296260977482530816,2
+6296282967715086336,5
+6296291763808108544,9
+6296297261366247424,7
+6296309355994152960,5
+6296384122784841728,6
+6296472083715063808,4
+6296507268087152640,8
+6296529258319708160,6
+6296557106887655424,1
+6296577636831330304,6
+6296876703994085376,4
+6297439653947506688,6
+6298002603900928000,9
+6299409978784481280,6
+6301661778598166528,4
+6303913578411851776,9
+6306165378225537024,1
+6307572753109090304,5
+6307871820271845376,2
+6307907004643934208,0
+6307928994876489728,2
+6307937790969511936,3
+6307972975341600768,1
+6307981771434622976,9
+6308294032736911360,3
+6308314579860455424,1
+6308333615155511296,9
+6308342411248533504,2
+6308364401481089024,7
+6308399585853177856,0
+6308487546783399936,6
+6308909759248465920,0
+6309261602969354240,4
+6309824552922775552,0
+6310176396643663872,2
+6310378431905267712,1
+6310383104829685760,3
+6310391900922707968,8
+6310400697015730176,5
+6310515046225018880,6
+6310523842318041088,8
+6310598609108729856,6
+6310739346597085184,5
+6310814113387773952,0
+6310822909480796160,2
+6310937258690084864,4
+6310946054783107072,5
+6310954850876129280,0
+6311161559062151168,0
+6311513402783039488,2
+6312920777666592768,6
+6315172577480278016,5
+6316579952363831296,7
+6317142902317252608,9
+6317494746038140928,5
+6317635483526496256,9
+6317723444456718336,3
+6317758628828807168,0
+6317780619061362688,7
+6317789415154384896,3
+6317807007340429312,1
+6317828997572984832,1
+6317916958503206912,0
+6318268802224095232,8
+6318620645944983552,7
+6318695412735672320,0
+6318704208828694528,4
+6318820001146994688,7
+6318987058194939904,2
+6318994479898427392,6
+6319020868177494016,8
+6319029664270516224,1
+6319038460363538432,7
+6319060450596093952,4
+6319095634968182784,0
+6319130819340271616,7
+6319240770503049216,1
+6319249566596071424,8
+6319254033362059264,3
+6321422201572556800,2
+6321452987898134528,3
+6321488172270223360,9
+6321576133200445440,1
+6321716870688800768,9
+6321804831619022848,0
+6321840015991111680,6
+6321862006223667200,4
+6321870802316689408,1
+6321889494014361600,4
+6321910384735289344,2
+6322209451898044416,8
+6322508519060799488,1
+6322530509293355008,5
+6322556897572421632,1
+6322562395130560512,1
+6322614072177065984,8
+6322636062409621504,1
+6322644858502643712,6
+6322649260844122112,5
+6322662450688688128,1
+6322671246781710336,2
+6322680042874732544,7
+6350238202313310208,8
+6350246998406332416,7
+6350268988638887936,1
+6350304173010976768,7
+6350326163243532288,7
+6350334959336554496,2
+6350378939801665536,3
+6350387735894687744,7
+6350409726127243264,6
+6350444910499332096,3
+6350470199266770944,8
+6350475696824909824,7
+6351007860452753408,0
+6351043044824842240,1
+6351078229196931072,1
+6351183782313197568,8
+6351482849475952640,2
+6352045799429373952,1
+6353453174312927232,2
+6355704974126612480,2
+6357112349010165760,5
+6357675298963587072,7
+6357961171986808832,8
+6357969968079831040,1
+6358065350713540608,3
+6358084317289119744,3
+6358093113382141952,6
+6358115103614697472,9
+6358150287986786304,6
+6358708839893696512,4
+6358717635986718720,0
+6358744024265785344,2
+6358752820358807552,1
+6358849577382051840,6
+6358858373475074048,0
+6358884761754140672,2
+6358893557847162880,5
+6359270690335490048,6
+6360255509156593664,6
+6360583507219054592,5
+6360639307434164224,5
+6360643980358582272,1
+6360652776451604480,1
+6360705553009737728,2
+6360723145195782144,6
+6360731941288804352,2
+6360753931521359872,1
+6360841892451581952,8
+6360929853381804032,8
+6360978231893426176,4
+6361000222125981696,9
+6361035406498070528,6
+6361123367428292608,9
+6361264104916647936,7
+6361615948637536256,5
+6361967792358424576,6
+6362055753288646656,7
+6362090937660735488,4
+6362112927893291008,0
+6362117600817709056,1
+6362139316172357632,6
+6362161306404913152,3
+6362183296637468672,8
+6362192092730490880,3
+6362209684916535296,2
+6362307541451407360,8
+6362390004823490560,9
+6362477965753712640,1
+6362499955986268160,3
+6362508752079290368,7
+6362526344265334784,7
+6362580495213002752,9
+6362587916916490240,4
+6363046413265272832,8
+6363076100079222784,4
+6363111284451311616,9
+6363146468823400448,9
+6363234429753622528,1
+6363375167241977856,3
+6363458730125688832,8
+6363467526218711040,7
+6363476322311733248,2
+6363498312544288768,3
+6363533496916377600,5
+6363568681288466432,1
+6363603865660555264,9
+6363639050032644096,1
+6363661040265199616,5
+6363665713189617664,3
+6363688528055894016,7
+6363709418776821760,8
+6363731409009377280,7
+6363740205102399488,6
+6363757797288443904,3
+6364100844916310016,2
+6366001900520734720,4
+6366088761939329024,9
+6366097558032351232,5
+6366102230956769280,9
+6366115150218395648,8
+6366123946311417856,8
+6366132742404440064,6
+6366248466003263488,1
+6366277877939306496,9
+6366299868171862016,7
+6366388928613711872,3
+6366418615427661824,8
+6366440605660217344,9
+6366449401753239552,8
+6366466993939283968,5
+6366475790032306176,3
+6366503552700907520,2
+6366524168543928320,1
+6366559352916017152,7
+6366581343148572672,2
+6366590139241594880,6
+6464165199136948224,9
+6470165234089721856,4
+6470172930671116288,8
+6470181726764138496,4
+6470190522857160704,6
+6470212513089716224,4
+6470234503322271744,0
+6470243299415293952,3
+6470260891601338368,7
+6470335658392027136,3
+6470423619322249216,3
+6470445609554804736,2
+6470450282479222784,7
+6470533570485026816,7
+6470552537060605952,6
+6470559958764093440,5
+6470568754857115648,3
+6470577550950137856,3
+6470599541182693376,8
+6470634725554782208,1
+6470669909926871040,0
+6470757870857093120,3
+6470898608345448448,2
+6471039345833803776,0
+6471127306764025856,8
+6471162491136114688,8
+6471184481368670208,9
+6471212244037271552,7
+6471232859880292352,6
+6471254850112847872,6
+6471260347670986752,3
+6471281238391914496,3
+6471625385531408384,6
+6471713621339537408,5
+6471721043043024896,0
+6471729839136047104,3
+6471738635229069312,1
+6471760625461624832,6
+6471782615694180352,8
+6471791411787202560,9
+6471809003973246976,3
+6471883770763935744,2
+6472024508252291072,7
+6472165245740646400,4
+6472517089461534720,0
+6473080039414956032,6
+6473642989368377344,4
+6473994833089265664,0
+6474082794019487744,6
+6474104784252043264,3
+6474113580345065472,5
+6474131172531109888,2
+6474135845455527936,7
+6474188347135754240,2
+6474210337368309760,3
+6474352174368292864,7
+6474359870949687296,2
+6474368667042709504,8
+6474377463135731712,4
+6474399453368287232,5
+6474434637740376064,9
+6474469822112464896,9
+6474505006484553728,8
+6474526996717109248,4
+6474614957647331328,9
+6474620455205470208,6
+8741781545842376704,6
+8741790341935398912,1
+8741809033633071104,1
+8741820028749348864,1
+8741825526307487744,1
+8741834322400509952,1
+8741856312633065472,9
+8741891497005154304,7
+8741913487237709824,0
+8741922283330732032,3
+8741939875516776448,1
+8741945373074915328,5
+8742071816912109568,2
+8742102603237687296,5
+8742137787609776128,0
+8742167474423726080,1
+8742326903609753600,5
+8742348893842309120,3
+8742400570888814592,9
+8742419262586486784,2
+8742454446958575616,7
+8742542407888797696,3
+8742630368819019776,3
+8742652359051575296,4
+8742674074406223872,8
+8742678747330641920,8
+8742700737563197440,8
+8742735921935286272,7
+8742823882865508352,6
+8742911843795730432,9
+8742947028167819264,8
+8742982212539908096,3
+8743008325941067776,6
+8743012998865485824,2
+8743020695446880256,6
+8743077870051524608,4
+8743083367609663488,9
+8743091064191057920,9
+8743369240632885248,8
+8743394529400324096,1
+8743400026958462976,4
+8934968762499596288,9
+8934996525168197632,5
+8935005321261219840,6
+8935014117354242048,9
+8935109409793638400,4
+8935128466563530752,8
+8935137262656552960,5
+8935159252889108480,0
+8935181243121664000,7
+8935193337749569536,3
+8935198835307708416,4
+8935207631400730624,8
+8935229621633286144,8
+8935264806005374976,3
+8935352766935597056,4
+8935427533726285824,9
+8935453922005352448,1
+8935462718098374656,3
+8935471514191396864,1
+8935480310284419072,3
+8935612251679752192,6
+8936852500795883520,6
+8936861296888905728,1
+8936883287121461248,6
+8936918471493550080,4
+8936949257819127808,9
+8937059208981905408,5
+8937094393353994240,4
+8937129577726083072,7
+8937164762098171904,9
+8937186752330727424,1
+8937195548423749632,6
+8937230732795838464,5
+8937239528888860672,0
+8937274713260949504,5
+8937283509353971712,8
+8937305499586527232,5
+8937340683958616064,9
+8937375868330704896,3
+8937411052702793728,3
+8937494615586504704,1
+8937516605819060224,9
+8937604566749282304,4
+8937696925726015488,4
+8937705721819037696,6
+8937727712051593216,9
+8937762896423682048,2
+8937784886656237568,9
+8937793682749259776,5
+8938325846377103360,6
+8938361030749192192,7
+8938396215121281024,5
+8938447892167786496,0
+8938453389725925376,4
+8938479778004992000,1
+8938501768237547520,8
+8938536952609636352,0
+8938642505725902848,8
+8938677690097991680,8
+8938712874470080512,2
+8938734864702636032,1
+8938743660795658240,7
+8939275824423501824,0
+8939302143983091712,1
+8939306610749079552,7
+8939315406842101760,6
+8939410789475811328,3
+8962888936141619200,2
+8962897732234641408,4
+8962919722467196928,2
+8962954906839285760,8
+8962984232875982848,1
+8963060459955552256,6
+8963085748722991104,2
+8963091246281129984,6
+8963100042374152192,7
+8963478274374107136,1
+8963485970955501568,0
+8966811993629523968,6
+8966825119049580544,0
+8966829585815568384,5
+8966838381908590592,7
+8966860372141146112,9
+8966895556513234944,5
+8966917546745790464,0
+8966926342838812672,3
+8966970323303923712,4
+8966979119396945920,9
+8967001109629501440,8
+8967036294001590272,5
+8967058284234145792,6
+8967067080327168000,4
+8967524477164322816,7
+8967533273257345024,3
+8967568457629433856,7
+8967577253722456064,8
+8967599243955011584,2
+8967634428327100416,1
+8967669612699189248,0
+8967691602931744768,4
+8967717991210811392,8
+8967726787303833600,9
+8967753175582900224,9
+8967775165815455744,5
+8967810350187544576,9
+8967915903303811072,0
+8967951087675899904,2
+8967986272047988736,8
+8968536027861876736,1
+8968544823954898944,1
+8968553620047921152,7
+8968580008326987776,8
+8968588804420009984,0
+8968685561443254272,6
+8968694357536276480,7
+8968720745815343104,5
+8968729541908365312,6
+8969477209815252992,0
+8969551976605941760,0
+8969626743396630528,2
+8969635539489652736,3
+8969644335582674944,2
+8969695737751273472,8
+8969723500419874816,0
+8969745490652430336,5
+8969833451582652416,9
+8969921412512874496,8
+8969956596884963328,5
+8969978587117518848,0
+8969987383210541056,5
+8970136916791918592,6
+8970145712884940800,1
+8970154508977963008,6
+8970180897257029632,7
+8970255664047718400,4
+8970396401536073728,1
+8970513684208025600,3
+8972665793535803392,4
+8972700977907892224,2
+8972736162279981056,6
+8972841715396247552,4
+8972876899768336384,1
+8972912084140425216,9
+8972934074372980736,3
+8972942870466002944,4
+8973285918093869056,6
+8973294714186891264,0
+8973303510279913472,1
+8973338694652002304,3
+8973347490745024512,4
+8973369480977580032,1
+8973404665349668864,6
+8973439849721757696,6
+8973461839954313216,8
+8973488228233379840,8
+8973497024326402048,8
+8973523412605468672,7
+8973545402838024192,4
+8973580587210113024,8
+8973615771582201856,3
+8973637761814757376,8
+8973646557907779584,1
+8973653979611267072,1
+8973681742279868416,7
+8973690538372890624,4
+8975462951116865536,5
+8975603688605220864,2
+8975744426093576192,2
+8975885163581931520,5
+8976002536448196608,8
+8977230897094852608,2
+8977235363860840448,0
+8977323324791062528,4
+8977345315023618048,4
+8977433275953840128,0
+8977515464448016384,1
+8977596003674750976,0
+8977604799767773184,5
+8977613595860795392,2
+8977631188046839808,1
+8977639984139862016,4
+8977661974372417536,8
+8977697158744506368,8
+8977719148977061888,3
+8977727945070084096,2
+8977763129442172928,7
+8977770482426183680,6
+8977824702093328384,1
+8977833498186350592,9
+8977842294279372800,7
+8977867308168904704,2
+8978629269726953472,9
+8978633942651371520,7
+8978660330930438144,5
+8978669127023460352,3
+8978677923116482560,6
+8978685254625656832,3
+8986422883022536704,0
+8987158456301518848,8
+8987166152882913280,9
+8987174948975935488,9
+8987254113813135360,9
+8987262909906157568,2
+8987270606487552000,4
+8988494362929266688,8
+8988501698733408256,1
+8988554836068794368,6
+8988573527766466560,4
+8988582323859488768,2
+8988604314092044288,5
+8988692275022266368,9
+8988780235952488448,9
+8988828614464110592,5
+8988850604696666112,8
+8988885789068754944,2
+8988920973440843776,0
+8988956157812932608,8
+8988978148045488128,6
+8988982820969906176,7
+8989026526557110272,5
+8989048516789665792,9
+8989066108975710208,6
+8989074905068732416,2
+8989096895301287936,1
+8989122184068726784,4
+8989127681626865664,3
+8989135378208260096,6
+8989326693231493120,7
+9127270322540642304,9
+9127279118633664512,5
+9127301108866220032,8
+9127336293238308864,8
+9127367079563886592,4
+9127441846354575360,0
+9127468165914165248,3
+9127472632680153088,8
+9127481428773175296,9
+9127858286383595520,4