Description

给定$n$组数据$a_i,b_i,m_i$，对于每组数求出一个 $x_i$，使其满足 $a_i×x_i≡b_i$(mod  $m_i$)，如果无解则输出 impossible。

Input Format

第一行包含整数 $n$。
接下来$n$行，每行包含一组数据 $a_i,b_i,m_i。$

Output Format

输出共$n$行，每组数据输出一个整数表示一个满足条件的$x_i$，如果无解则输出 impossible。
每组数据结果占一行，结果可能不唯一，输出任意一个满足条件的结果均可。
输出答案必须在$int$范围之内。

2
2 3 6
4 3 5

impossible
-3

Hint

$1≤n≤10^5$,
$1≤a_i,p_i≤2∗10^9$

Source

2.4数学知识 扩展欧几里得算法