ATM Game

Interview

Time limit1sMemory limit128 MB

Summary

Given two bill denominations a and b and an amount S, find non-negative counts of each summing to S with the fewest total bills, or report Impossible.

Level: Medium6 of 10
Topics: Math, Number theory, Greedy, Brute force
Solved: No attempts yet

Problem

An ATM holds a very large supply of two different denominations of bills. When money is withdrawn, the ATM dispenses exactly the requested amount, as long as it does not exceed the account holder's balance. The customer prefers to carry as few bills as possible, so they want to use the smallest possible total number of bills.

Write a program that dispenses the requested amount exactly while using the minimum total number of bills. You may assume the ATM contains an unlimited supply of each denomination.

Input

The first line contains the number of test cases $T$ . Each test case is given on a single line containing the two denominations $a$ and $b$ held by the ATM and the amount $S$ to withdraw, separated by spaces.

Output

For each test case, print the number of bills of denomination $a$ followed by the number of bills of denomination $b$ , in this order and separated by a space, that dispense exactly $S$ using the minimum total number of bills. If it is impossible to dispense the amount exactly, print "Impossible" (without the quotes).

Constraints

$1 \le T \le 100$
$1 \le a, b \le 10000$
$a \ne b$
$0 \le S \le 10^9$

Examples3

Example 1

Input

Expected output

3 2
1 2
Impossible

Example 2
Input
```
1
5 7 0
```
Expected output
```
0 0
```
Example 3
Input
```
1
2 7 100
```
Expected output
```
1 14
```