题目背景

在开锁公司劳动

题目描述

这天，WD发现了一个很奇怪的密码锁，他记得CX让他解开这个密码锁之前告诉过他一些数字，可惜由于WD菜的真实，早就忘了那些数字是啥，只记得把他们从1到$n$编号后，对于任意的正整数$d(1\le d\le n)$，编号为$d$的倍数的数字之和恰好等于$\mu(d)$（即$d$的莫比乌斯函数值）。

现在，由于要打开这个密码锁，他必须知道第$m$个位置上的数字。由于他什么都不会，当然要请你来帮忙啦……

输入格式

第一行一个数$T$，表示数据组数。接下来$T$行每行两个数，分别为$n,m$。

输出格式

共$T$行，每行一个数字，表示第$m$个数字的值。显然可以证明解是唯一的。

2
5 1
5 2

4
-1

提示

$subtask1(21pts):~n\le 10^6,~T\le 5$

$subtask2(34pts):~n\le 10^7,~T\le 10$

$subtask3(45pts):~n\le 10^{18},~m\le 10^9,~\frac{n}{m}\le 10^9,~T\le 20$

对于所有数据，$m\le n$。

对于样例1，满足要求的数列为4 -1 -1 0 -1.