Problem Background

$\rm$ is recently working on the price system for a newly built universal shopping mall.

Problem Description

The shopping mall gathers goods from various planets, but since different planets use different number bases, calculating the prices of goods is quite challenging. Therefore, a price system is essential.

Given the tight deadline from the client, $\rm$ has asked you to assist him by writing a program for base conversion. He will handle all other system modules himself. Can you write the conversion program within the deadline?

Input and Output Format

Input Format

The first line contains a number \( n \), indicating how many item prices need to be converted.

Next, \( n \) lines follow, each containing three numbers \( a, l, r \) and a price string \( S \).

\( a \) indicates that the price string is in base \( a \) (guaranteed \( a \) is not \(-1, 0, 1\)), and you need to convert it to all bases from \( l \) to \( r \) (skipping bases \(-1, 0, 1\)).

Since prices are real numbers, there may be decimals, and if a decimal is recurring, the repeating part will be enclosed in <,>.

If it's not a recurring decimal, there will be no angle brackets. If there is no fractional part, there will be no decimal point. The repeating part and the fractional part before it are guaranteed to be the shortest. For example, in base 10, \( 0.123123\cdots \) will be given as \( 0.<123> \), and situations like \( 0.1<231> \) or \( 0.<123123> \) will not occur.

For positive bases \( a \), the repeating part will not be \( a-1 \). For example, in base 10, \( 0.<9> \) will not occur, but this restriction does not apply to negative bases.

When representing negative numbers in positive bases, a negative sign is added before the price. However, since negative bases can represent both positive and negative numbers, no negative sign is allowed before negative bases.

Each digit in any base cannot be negative, and values greater than 9 are represented by uppercase letters in ascending order.

Output Format

For each price to be converted, output the converted price strings in ascending order of bases within the given range (skipping bases \(-1, 0, 1\)).

The output format should strictly follow the requirements as specified in the input format.

Sample Input and Output

Sample Input #1

2
10 2 4 72451
-3 -4 2 123456

Sample Output #1

10001101100000011
10200101101
101230003
2021
122000
10001001
-10000111

Sample Input #2

2
8 2 2 176336030760401.6
30 35 36 HQA9MBFD3SEC.<GAR85DJ2LO>

Sample Output #2

1111110011011110000011000111110000100000001.11
39SAWRJ5CPP7.<J36CPFVSM9>
2EMEUXKKZHA0.<JMWQ6>

Sample Input #3

1
-26 -6 -6 1PMMK.<L15>

Sample Output #3

1213400.<511>

Notes

• For \( 5\% \) of the data, there is no fractional part, \( 1 \leq n \leq 20, 2 \leq a \leq 36, 2 \leq l \leq r \leq 36 \);
• For \( 15\% \) of the data, there is no fractional part, \( 1 \leq n \leq 100, 2 \leq |a| \leq 36, -36 \leq l \leq r \leq 36 \);
• Another \( 15\% \) of the data guarantees that both the original and converted numbers are finite decimals, \( 1 \leq n \leq 550, 2 \leq a \leq 36, 2 \leq l \leq r \leq 36 \);
• Another \( 20\% \) of the data, \( 1 \leq n \leq 550, 2 \leq a \leq 36, 2 \leq l \leq r \leq 36 \);
• For \( 100\% \) of the data, \( 1 \leq n \leq 550, 2 \leq |a| \leq 36, -36 \leq l \leq r \leq 36 \);

The absolute value of the price in all data will not exceed \( 2^{63}-1 \), and the string length of the fractional part before and after conversion will not exceed \( \left\lfloor \log_{|a|} 2^{62} \right\rfloor \) (excluding the brackets).

见题面 Input 部分

见题面 Output 部分