Последовательность лампочек

Сейчас происходит подготовка к церемонии открытия очередных голодных игр. В качестве одного из декоративных элементов будет выступать последовательность лампочек, расположенных над сценой. Последовательность состоит из $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$ строках выведите ответы для каждого из вариантов.