找到余数循环节

题目描述

定义 r_n=a^n mod m，n 从0开始，因此 r_0=1 mod m。序列首次出现重复状态后进入循环，求重复前的前导段长度和循环长度。

输入格式

一行输入 a、m，满足 0≤a≤10^9、1≤m≤2×10^5。

输出格式

输出两个整数：前导段项数 μ 和最短循环长度 λ。

样例

输入

2 5

输出

0 4