SIRNUMS - SIR CHIRAG AND MAGIC NUMBERS

Sir Chirag is famous for his 'Intelligencia". He found that Dukkar and Chapta were unable to solve a question.

The magic Numbers are described as: The numbers are strictly positive, don't contain any leading zeroes. It has exactly 'p' digits and if we move the last digit of the number to the beginning, it grows exactly 'x' times.

Chirag Sir took the task to solve it. It took him minutes to solve. Now its your turn.

You have to find the minimum possible number that satisfies the above conditions given 'p' and 'x'.

Input

First line contains the number of test cases T: 0 < T <= 50

Next T lines contains two integers p and x, 0 < p <= 1000000 and 0 < x < 10.

Output

If such a number is not possible then print "Impossible" (Without the quotes). Else print the number.

Example

Input:
3
6 5
1 2
6 4

Output:
142857
Impossible
102564

(observe that for the first test case : 142857 x 5 = 714285)


Added by:pika_pika
Date:2014-03-27
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Codeforces

hide comments
2018-02-09 21:05:42
It seems testcases have been strengthened sometime mid'2015 without rejudging. It doesn't seem possible to AC in raw Python anymore, let alone in 0.00s as some early scores show. I doubt one can output 1MB of data in C in that time.. So don't get frustrated if you can't get a high spot in the ranks.
2014-05-05 11:35:58 Flago
@psetter : Could you give me a case where my solution is failing (submission : 11527636)? Thx
-----ans--> please read the problem statement carefully. it asks for smallest. the incorrect ans that is generated satisfies the logic but is not the smallest hence ruled out.

Last edit: 2014-05-14 19:46:10
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.