시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB75375.000%

문제

Сейчас происходит подготовка к церемонии открытия очередных голодных игр. В качестве одного из декоративных элементов будет выступать последовательность лампочек, расположенных над сценой. Последовательность состоит из $n$ лампочек, пронумерованных от $1$ до $n$.

Изначально все лампочки выключены. Уже решено, что во время церемонии с лампочками будут производить $k$ действий. Во время $i$-го ($1 \le i \le k$) действия инвертируют состояния всех лампочек, номера которых делятся на $i$. При инвертировании, если лампочка была выключена, она загорается, и наоборот. Причем, по, известной одному только главному дизайнеру, причине $n$ не превышает $10 \cdot k$.

Теперь главного дизайнера заинтересовал вопрос, какое количество лампочек останутся гореть после выполнения всех действий. Помогите ему.

Пока что не до конца определились с количеством лампочек и количеством действий над ними. Всего есть $t$ возможных вариантов. Главный дизайнер предоставил вам список из $t$ возможных пар $n_i$ и $k_i$. Для каждого варианта выведите количество лампочек, которые останутся гореть в конце.

입력

В первой строке находится одно целое число $t$ ($1 \le t \le 100$) --- количество возможных вариантов.

В следующих $t$ строках находятся пары чисел $n_i$ и $k_i$ ($1 \le n_i \le 10^{18}$, $1 \le k_i \le 10^{18}$, $n_i \le 10 \cdot k_i$).

출력

В $t$ строках выведите ответы для каждого из вариантов.

예제 입력 1

2
8 5
5 1

예제 출력 1

5
5