Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Same GCDs

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given two integers $$$a$$$ and $$$m$$$. Calculate the number of integers $$$x$$$ such that $$$0 \le x < m$$$ and $$$\gcd(a, m) = \gcd(a + x, m)$$$.

Note: $$$\gcd(a, b)$$$ is the greatest common divisor of $$$a$$$ and $$$b$$$.

Input

The first line contains the single integer $$$T$$$ ($$$1 \le T \le 50$$$) — the number of test cases.

Next $$$T$$$ lines contain test cases — one per line. Each line contains two integers $$$a$$$ and $$$m$$$ ($$$1 \le a < m \le 10^{10}$$$).

Output

Print $$$T$$$ integers — one per test case. For each test case print the number of appropriate $$$x$$$-s.

Example

Input

3 4 9 5 10 42 9999999967

Output

6 1 9999999966

Note

In the first test case appropriate $$$x$$$-s are $$$[0, 1, 3, 4, 6, 7]$$$.

In the second test case the only appropriate $$$x$$$ is $$$0$$$.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/23/2021 12:34:19 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|