최소공배수의 합

$n$과 $m$이 주어진다. 아래 두 조건을 모두 만족하는 양의 정수 쌍 $(x, y)$에 대해, $x$와 $y$의 최소공배수를 모두 더한 값을 구하는 프로그램을 작성하시오.

1. $1 \le x \le n$, $1 \le y \le m$
2. $z > 1$인 정수 $z$ 중에서 $z^2$이 $x$와 $y$를 동시에 나누는 것은 하나도 없다.

첫째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 200$)가 주어진다. 이어지는 $T$개의 줄에 각각 두 정수 $n$과 $m$ ($1 \le n, m \le 4\,000\,000$)이 주어진다.

각 테스트 케이스마다 구한 합을 $2^{30}$으로 나눈 나머지를 한 줄에 하나씩 출력한다.