405885: GYM102152 C Large GCD

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Large GCDtime limit per test1.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This problem is very simple so the problem setters decided that its statement should be simple too. You are given two integers $$$n$$$ and $$$m$$$ such that $$$\text{gcd}(n,\,m) \equiv 1$$$, and your task is to find the value of the function $$$\text{F}(n,\,m)$$$ as follows:

$$$\text{F}(n,\,m) = \text{gcd}(5^n + 7^n,\,5^m + 7^m)$$$

In mathematics, the greatest common divisor (gcd) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For example, the gcd of $$$8$$$ and $$$12$$$ is $$$4$$$.

Input

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

Each test case consists of a single line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^9,\, \text{gcd}(n,\,m) \equiv 1$$$).

Output

For each test case, print a single line containing the value of the function $$$\text{F}(n,\,m)$$$ as described in the statement.

ExampleInput
2
2 3
5 3
Output
2
12
Note

In the first test case, the value of the function can be found as follow: $$$$$$\text{F}(2,\,3) = \text{gcd}(5^2 + 7^2,\,5^3 + 7^3)$$$$$$ $$$$$$\text{F}(2,\,3) = \text{gcd}(74,\, 468)$$$$$$ $$$$$$\text{F}(2,\,3) = 2$$$$$$

In the second test case, the value of the function can be found as follow: $$$$$$\text{F}(5,\,3) = \text{gcd}(5^5 + 7^5,\,5^3 + 7^3)$$$$$$ $$$$$$\text{F}(5,\,3) = \text{gcd}(19932,\, 468)$$$$$$ $$$$$$\text{F}(5,\,3) = 12$$$$$$

加入题单

上一题 下一题 算法标签: