전구 배열

곧 열릴 헝거 게임 개막식을 준비하고 있다. 장식으로 무대 위에 전구 한 줄을 달기로 했다. 전구는 $n$개이며, 번호는 1번부터 $n$번까지 매겨져 있다.

처음에는 모든 전구가 꺼져 있다. 개막식 중에 전구를 대상으로 $k$번의 동작을 수행한다. $i$번째 ($1 \le i \le k$) 동작에서는 번호가 $i$의 배수인 전구들의 상태를 모두 반전한다. 꺼져 있던 전구는 켜지고, 켜져 있던 전구는 꺼진다. 주 디자이너만 아는 이유로 $n$은 $10k$를 넘지 않는다.

디자이너는 모든 동작이 끝난 뒤 켜진 채로 남아 있는 전구가 몇 개인지 알고 싶어 한다. 그를 도와 그 개수를 구하자.

전구 개수와 동작 횟수는 아직 확정되지 않았다. 가능한 경우는 모두 $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 10k_i$).

$t$개의 줄에 각 경우의 답을 출력한다.