两台转盘同时归位

题目描述

给定 a、b、m，数据保证 gcd(a,m)=gcd(b,m)=1。求最小正整数 t，使 a^t≡1 (mod m) 且 b^t≡1 (mod m)。

输入格式

一行输入 a、b、m，满足 0≤a,b≤10^9、1≤m≤2×10^5，并满足互质保证。

输出格式

输出最小正整数t。特别地，m=1时所有整数同余，答案规定为1。

样例

输入

2 3 5

输出

4