12651265 SUSTech Online Judge
Problem 1265 --Eccentric calculator

1265: Eccentric calculator

Time Limit: 3 Sec  Memory Limit: 20 MB
Submit: 1043  Solved: 206
[Submit][Status][Web Board]

Description

Yuki is a clever girl and she is playing an eccentric calulator. The eccentric calculator can only display \(n\) digits, which really annoys her.

She enters a number \(m\) in the calculator first, and then just repeatedly squares it until the result overflows. When it overflows, only the \(n\) most significant digits can still be displayed on the screen, and an error will appear at the same time. Yuki can clear the error flag and continue squaring the displayed number. She wonders what is the largest number she can get by repeatedly doing this procedure for given \(n\) and \(m\).

Input

The first line contains an integer \(t\) (\(1 \leq t \leq 200\)) — the number of test cases. Each test case contains one line with two integers: \(n\) and \(m\) (\(1 \leq n \leq 9, 0 \leq m < 10^{n}\)) — the number of digits and the starting number.

Output

For each test case, print one line with the maximum number that Yuki can obtain.

Sample Input

2
1 5
2 99

Sample Output

5
99

HINT

Yuki can obtain \(5 \rightarrow 2(5) \rightarrow 4 \rightarrow 1(6) \rightarrow 1 \rightarrow 1 \rightarrow \cdots\) respectively in the first case by repeatedly squaring it.

Source

2019Fall_DSAA_Lab3 

[Submit][Status]