505033 - 二次模方程

给出一个一元二次方程ax^2+bx+c,以及一个质数p,请找出所有满足(ax^2+bx+c)%p=0条件下的x。

Input

第一行1个数T对应测试的数量(1≤T≤50000)。 之后T行,每行4个数a,b,c,p(1≤a,b,c<p≤1000000000,p为质数)。

Output

输出共T行,对应每个询问的结果,如果不存在则输出“No Solution”。

Examples

Input

3

Output

1
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题