F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Pass!

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 2395    Accepted Submission(s): 677


Problem Description
There are \(n\) players passing ball on the football field.

Initially, the first player has the ball. Then each second, the player with ball should pass the ball to any other player.

Alice wonders how many way to pass the ball, such that after \(t\) seconds, the ball will turn back to the first player. So she asks Bob for help.

Now, Bob solved the question and found that the answer modulo \(998244353\) is \(x\). But he forgot the exact number of \(t\). So he ask you for help, to find the smallest non-negative integer \(t\), such that the answer of Alice's question modulo \(998244353\) will be \(x\).
 

Input
The first line contains an integer $T(1\le T\le 100)$representing the number of test cases.

For each test case, there are two integers $n,x(2\le n\le 10^{6}, 0\le x < 998244353)$in one line.
 

Output
For each test case, output a single line containing one integer indicates the smallest $t$. If such $t$ do not exist, output \(-1\) instead.
 

Sample Input
5 11 1 11 0 11 10 11 76805204 11 2
 

Sample Output
0 1 2 233333 -1
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-28 20:11:08, Gzip enabled