CF1485C Floor and Mod

A pair of positive integers $(a,b)$ is called special if $\left\lfloor\frac{a}{b}\right\rfloor=a \bmod b$. Here, $\left\lfloor\frac{a}{b}\right\rfloor$ is the result of the integer division between $a$ and $b$, while $a \bmod b$ is its remainder.

You are given two integers $x$ and $y$. Find the number of special pairs $(a,b)$ such that $1≤a≤x$ and $1≤b≤y$.

Input

The first line contains a single integer $t$ ($1≤t≤100$) — the number of test cases.

The only line of the description of each test case contains two integers $x$, $y$ ($1≤x,y≤10^9$).

Output

For each test case print the answer on a single line.

Example

input

9
3 4
2 100
4 3
50 3
12 4
69 420
12345 6789
123456 789
12345678 9

output

1
0
2
3
5
141
53384
160909
36

Note

In the first test case, the only special pair is $(3,2)$.

In the second test case, there are no special pairs.

In the third test case, there are two special pairs: $(3,2)$ and $(4,3)$.

Idea

令 $a=kb+m$，有 $k,m\in\mathbb N$，且 $k\geq 0,0\leq m<b$；那么 $\left\lfloor\frac{a}{b}\right\rfloor=k=m$，将 $k$ 用 $m$ 代替，得到 $a=(b+1)m$；可以看到，$m=0$ 是不可行的。

首先枚举 $b$，已知 $1\leq b\leq y$。当 $b$ 确定时，枚举 $m$，可得 $a$；已知 $1\leq a\leq x$，故得到不等式组 $1\leq m<b$ 和 $1\leq (b+1)m\leq x$。

显然，$m$ 的上限值为 $\min\left(\left\lfloor\frac{x}{b+1}\right\rfloor,b-1\right)$。

综上所述，答案为 $\sum\limits_{b=1}^y\min\left(\left\lfloor\frac{x}{b+1}\right\rfloor,b-1\right)$。

令 $\frac{x}{b+1}\le b-1$，得到 $b\ge\sqrt{x+1}$；可知 $\sqrt{x+1}$ 附近有 $B$，是满足 $\left\lfloor\frac{x}{b+1}\right\rfloor\le b-1$ 最小的 $b$。

$\begin{aligned}\text{answer}&=(0+1+2\cdots +B-2)+\left(\left\lfloor\frac{x}{B+1}\right\rfloor+\left\lfloor\frac{x}{B+2}\right\rfloor+\cdots+\left\lfloor\frac{x}{y+1}\right\rfloor\right)\\&=\sum\limits_{i=1}^{B-2}i+\sum\limits_{i=B+1}^{y+1}\left\lfloor\frac{x}{i}\right\rfloor\end{aligned}$

求等差数列和数论分块。

Code

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: CF1485C
Date: 2021 Feb. 28th
Description: Number Theory, Counting
*******************************************************************/
#include<cmath>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=100005;
int _;
int main(){
	for(cin>>_;_;_--){
		ll x,y;
		cin>>x>>y;
		ll B=sqrt(x+1);
		while(x/(B+1)>B-1){
			//找到取x/(B+1)的临界值
			B++;
		}
		ll ans=0;
		if(B-1>y){
			//全都取b-1
			ans+=y*(y-1)/2;
		}else{
			ans+=(B-1)*(B-2)/2;
		}
		for(ll l=B+1,r;l<=y+1;l=r+1){
			if(l>x){
				//除数为0
				break;
			}
			r=min(x/(x/l),y+1);
			ans+=(x/l)*(r-l+1);
		}
		cout<<ans<<endl;
	}
	return 0;
}