Problem E: Strfry

strfry

In the C programming language, strings are not a native data type. In fact, they are just an array of characters, with a sentinel NULL value used to denote the end of the string. Since working with strings is a very important thing to do in programming languages, the C standard library has several very useful functions for string manipulation: among them are strcpy, strcmp, strtol, strtok, strlen, and strcat.

However, there is one function that not many know about, and even fewer use it: the strfry function. strfry takes an input string and randomly swaps a random number of characters.

Given two strings, determine if it is possible that the second string is the first string, strfried.

Input Format

The input begins with a number 0 < N < 1001, the number of test cases.

Each test case consists of a single line containing two strings of lowercase English characters, separated by a single space; these are the two strings in question. Each string is at most 1000 characters long.

Output Format

Output one line for each test case, containing either "Impossible" or "Possible" (without quotes).

Sample Input

4
a a
ab ba
ring gnir
newt twan

Sample Output

Possible
Possible
Possible
Impossible

Kent Williams-King
CCPC 2014