← 返回题目列表

AtCoder · tricky_3

C. 阶乘和质因数

中文机器翻译题面 查看原题

問題文

N! = 1 \times 2 \times ... \times N 中包含的素因数 p 的数量 我们将其表示为 F(N,\ p) 。(但是 p 是素数) 也就是说,对于
,使N!/p^k 成为整数的最大非负整数 k 是 在 F(N,\ p) 。
例如, 当分解为N=12 什么时候 12! = 479001600 = 2^{10} \times 3^5 \times 5^2 \times 7 \times 11 ,所以F(12,\ 2) = 10,\ F(12,\ 3) = 5,\ F(12,\ 47) = 0 等等。

今,素数 p 和整数 可以获得第 x ,所以N-F(N,\ p) = x 变成最小的非负整数 N 。
此外, 负文字,例如0! = 1 。

入力

第一行是测试用例的数量 T 。
之后的行包括 T 测试用例如下。

每个测试用例都是 仅由 1 行组成,以半角空格分隔。 p,\ x 。

制約

  • 0 \leq T \leq 5000
  • 2 \leq p \leq 47 在 p 是质数
  • 0 \leq x \leq 50 在 x 是一个整数

出力

对于每个测试用例,N-F(N,\ p) = x 变成最小的非负整数 N 。
但是,如果那样的 N 不存在 -1 请(去掉单引号)输出。

入力例

2
5 0
47 50

出力例

0
51

作者:laycrs 一组