Problem E: Eccentric calculator

Problem E: Eccentric calculator

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


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\).


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.


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

Sample Input

1 5
2 99

Sample Output



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.