Basic Gcd Problem
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

As a great ACMer, ZYB is also good at math and number theory.

ZYB constructs a function f_c(x) such that:
.
Give some positive integer pairs (n_i, c_i), ZYB wants to know .

输入描述:

The input contains multiple test cases. The first line of input contains one integer .
In the following  lines, each line contains two integers n_i, c_i () describing one question.

输出描述:

For each test case, output one integer indicating the answer.
示例1

输入

复制 
2
3 3
10 5

输出

复制 
3
25