29062번 - Последовательность лампочек 다국어

문제

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

제한

힌트