Daisy and the Password

3.6

771 votes
String, Implementation, Hiring, Easy, Ready, Approved
Problem

Daisy, being a good hacker as we all know, recently came across a file of the evil organization-Hydra which requires a password to open, and you have been assigned the task to help her in it.

She knows that the password of Hydra files are usually made from a list of words that Daisy already has. The password is made by taking a single word, let's say W, and making its copy WC. WC is then inserted anywhere in W only once, which gives us the required password.

For example, if we consider the word- "Hydra", the passwords that are possible are: "HydraHydra", "HHydraydra", "HyHydradra", "HydHydrara" and so on...

Now, given two strings S and P, you need to tell if P is a possible password which can be made from the word S, using the above rules. Print "Possible" (without the quotes) if possible, and "Impossible"(without the quotes) if it's not.


Input Format:
First line contains T, the number of test cases. T lines follow.
Each line consists of two space separated strings, S and P. S and P consists of characters 'a'-'z' and 'A'-'Z'.


Output Format:
For each test case, print the answer- "Possible" or "Impossible" (without the quotes).


Constraints:
1 ≤ T ≤ 250
1 ≤ |S| ≤ 60
1 ≤ |P| ≤ 60

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Test Case 1: Explained in the description.

Test Case 2: The length of P should be exactly 10, when it's made up from S="Hydra".

Editor Image

?