C. Jumps on a Circle
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are p points on the circle numbered from 0 to (p - 1) in a way that from the point 0 you can move to the point 1, from the point 1 — to the point 2, and so on, and from the point (p - 1) you can move to the point 0.

A chip is initially placed at the point 0. It starts to jump around the circle, first moving 1 point forward, then 2 points forward, then 3 points forward and so on.

How many unique points (including the start one) will be visited by a chip after n moves?

Input

The input has two integers p and n (1 ≤ p ≤ 107, 0 ≤ n ≤ 1018) — the number of points on a circle and the number of moves.

Output

Output a single integer — the number of unique points visited by a chip.

Examples
Input
3 10
Output
2
Input
5 3
Output
3
Input
8 1000000000000000000
Output
8