backupkid's blog

Need help for a number theory problems !
By backupkid, history, 106 minutes ago, In English

Hi everyone!

I recently came across this problem and I’m not sure how to approach it efficiently. Any hints or ideas would be appreciated!

Problem Statement

Cyclic Divisibility

Given three positive integers $$$a, b, c$$$, we need to find the smallest positive integer $$$x$$$ such that:

$$$ a \cdot x \equiv 0 \pmod b $$$
$$$ b \cdot x \equiv 0 \pmod c $$$
$$$ c \cdot x \equiv 0 \pmod a $$$

---

Input

The first line contains an integer $$$T$$$ — the number of test cases ($$$1 \le T \le 10^5$$$).

Each of the next $$$T$$$ lines contains three integers $$$a, b, c$$$ ($$$1 \le a, b, c \le 10^6$$$).

Output

For each test case, print a single integer — the minimum value of $$$x$$$ satisfying the conditions.

Example

Input

2
4 6 10
12 34 56

Output

30
1428

Thanks for reading!
Any ideas or hints would be appreciated :)

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
66 minutes ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

In the example, I think you mistakenly wrote input again, pls fix it.

→ Reply
  • »
    »
    57 minutes ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    ahh okay , my bad !!

    → Reply
»
56 minutes ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Auto comment: topic has been updated by backupkid (previous revision, new revision, compare).

→ Reply
»
55 minutes ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

I'm not sure but I think answer is lcm(lcm(lcm(a,b),lcm(b,c)),lcm(c,a))

→ Reply
  • »
    »
    1 minute ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    This can be simplified to $$$\text{lcm}(a, \text{lcm}(b,c))$$$ since being a multiple of $$$b$$$ and $$$c$$$ implies being a multiple of $$$b,c$$$.

    → Reply