解题思路

设第 $j$ 盏灯被按的总次数为 $t(j)$。第 $i$ 个人会在 $i\mid j$ 或 $j\mid i$ 时按一次。

对固定的 $j$：

• 由“有人是 $j$ 的约数”带来的次数：满足 $i\mid j$ 且 $1\le i\le m$ 的个数，记为 $d_{\le m}(j)$。
• 由“有人是 $j$ 的倍数”带来的次数：满足 $j\mid i$ 且 $1\le i\le m$ 的个数，为 $\left\lfloor \frac{m}{j}\right\rfloor$。
• 两者交集只在 $i=j$ 时出现（当且仅当 $j\le m$），被双计了一次，需要减去 1 次。

题目内容

给有$n$盏灯(编号$1$~$n$)，初始均为关闭状态。现有$m$个人(编号$1$~$m$)，第$i$个人会对所有满足$i\ |\ j$或$j\ |\ i$的灯$j$各按一次开关。按一次开关指切换灯的当前状态(开变关，关变开)。

请在所有人按完后，输出最终亮着的灯的数量。

[名词解释]

整除符号: $i\ |\ j$表示$i$整除$j$(即$j\ mod\ i =0$)，$i \nmid j$表示不整除;“$i\ |\ j$或j$j\ | \ i$"指二者存在因倍关系之一。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T (1≦T≦10^5)$表示数据组数。每组测试数据描述如下:

一行输入两个整数

$n,m (1≦n≦10,1≦m ≤10^{18})$

保证所有测试中$n$的总和不超过$2×10^6$

输出描述

输出$T$行，每行输出一个整数，表示所有人按完后仍然亮着的灯的数量

样例1

输入

3
5 3
4 1
6 2

输出

2
4 
2

说明

样例一: $n =5,m =3$。计算可得仅$j= 1,5$ 为开，答案$2$。

样例二: $m=1$时仅第$1$个人操作，因$1\ |\ j$对所有$j$成立，所有灯都被按一次，全部点亮，答案$4$。

样例三: $n =6,m =2$，最终仅$j=3,5$ 为开，答案$2$。