灯的开关

题目描述

给有 n 盏灯，编号为 1 到 n，初始时全部关闭。现在有 m 个人，编号为 1 到 m。

第 i 个人会对所有满足 i | j 或 j | i 的灯 j 按一次开关。其中：

• i | j 表示 i 整除 j
• j | i 表示 j 整除 i

按一次开关表示切换灯的当前状态，即亮变灭、灭变亮。

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

输入格式

第一行输入一个整数 T，表示测试数据组数。

接下来 T 行，每行输入两个整数 n、m，表示一组测试数据。

输出格式

输出 T 行，每行输出一个整数，表示对应测试数据中最终亮着的灯的数量。

数据范围

1 <= T <= 10^5

1 <= n <= 10

1 <= m <= 10^18

保证所有测试数据中 n 的总和不超过 2 * 10^6。

样例 1

输入

3
5 3
4 1
6 2

输出

2
4
2