Normal Sort

Time limit1sMemory limit128 MB

Summary
Implement a custom string comparator that treats embedded numeric runs (with optional signs) by numeric value and letters case-insensitively, then compare pairs of strings accordingly.
Level

Medium5 of 10

Topics
String, Implementation, Simulation
Solved
No attempts yet

Problem

Plain lexicographic sorting does not always order strings containing numbers as intended. For instance, xyz100 comes before xyz2. In this problem, you must write a comparison function for normal sort, which compares numeric runs inside strings by their numeric values. Under normal sort, the following order is produced.

XYZ001, XYZ2, XYZ003, XYZ08, XYZ23, XYZ100, XYZQ

The comparison rules are extended as follows.

  1. Letter case is ignored; letters are treated as uppercase.
  2. If + or - is followed by a digit and is not immediately after a digit, it is treated as the sign of the following numeric run. If + or - appears immediately after a digit, it is compared as a regular character.

Therefore 123+456+7890 is a string with three numeric runs separated by + characters, while A+003 compares the same as A3.

For each data set, two printable non-space ASCII strings are given. Compare them using the rules above. Output -1 if the first string comes first, 0 if they have the same order, and 1 if the second string comes first.

Input

The first line contains the number of data sets N (1 ≤ N ≤ 1000). Each of the next N lines contains two strings to compare, separated by one space. The strings contain no spaces.

Output

For each data set, output one of -1, 0, or 1 on its own line.

Examples1

  1. Example 1

    Input
    5
x-3 X0001
123-456-7890 123+456+7890
xYz000123J XyZ+123j
#$%^&*[]- abcdefgh
Abc47jKL+00123 ABC+47jkL123
    Expected output
    -1
1
0
-1
0