← 返回题目列表

AtCoder · arc094_b

D. 最坏的情况

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

分数: 700 点

问题陈述

10^{10^{10}} 包括高桥在内的参与者参加了两项编程竞赛。 在每场比赛中,所有参赛者都获得了从第一名到第二名的不同排名 10^{10^{10}}-th。 参赛者的

的 分数 是他/她在两次比赛中的排名的乘积。

处理以下内容 Q 查询:

  • 在 i-第查询,给你两个正整数 A_i 和 B_i。假设高桥排名 A_i- 第一场比赛中的第 B_i-在第二场比赛中,找出分数小于高桥分数的最大可能参赛人数。

约束

  • 1 \leq Q \leq 100
  • 1\leq A_i,B_i\leq 10^9(1\leq i\leq Q)
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

Q
A_1 B_1
:
A_Q B_Q

输出

对于每个查询,打印分数小于 Takahashi 的参与者的最大可能数量。


示例输入 1

8
1 4
10 5
3 3
4 11
8 9
22 40
8 36
314159265 358979323

示例输出 1

1
12
4
11
14
57
31
671644785

让我们表示排名的参与者 x- 第一场比赛中的第 y- 第二场比赛中的第 (x,y).

在第一个查询中, (2,1) 是分数低于 Takahashi 的参与者的可能候选者。永远不会有两个或更多参与者的分数小于高桥的分数,因此我们应该打印 1.