쉬운 측정

Edward는 두 대의 물 펌프의 양수량을 측정하는 일을 맡았다. 그는 펌프로 물탱크에 물을 퍼 넣고, 일정 시간 동안 탱크에 퍼진 물의 양을 확인했다.

그는 첫 번째 펌프가 $b$초 동안 $a$리터의 물을 퍼 올리고, 두 번째 펌프가 $d$초 동안 $c$리터의 물을 퍼 올린다는 것을 알아냈다. 또한 두 펌프를 동시에 사용하면 둘이 합쳐 $d$초 동안 $b$리터의 물을 퍼 올린다는 것도 알아냈다.

안타깝게도 Edward는 기록에 물을 쏟아서 이제 $a$와 $c$의 값을 복구할 수 없다. 하지만 두 값이 양의 정수였다는 것은 기억한다. 이제 그는 자신의 측정 결과와 일치하도록 $a$와 $c$의 값을 고르는 방법이 몇 가지인지 궁금해한다.

첫째 줄에는 정수 $n$ ($1\le n\le1000$)이 주어진다. 이는 테스트 케이스의 수이다.

다음 $n$개의 줄에는 각각 두 정수 $b$와 $d$가 주어진다 ($1\le b,d\le10^9$).

각 테스트 케이스마다 $a$와 $c$를 고르는 방법의 수를 나타내는 정수 하나를 출력한다. 각 답은 서로 다른 줄에 출력한다.

첫 번째 테스트 케이스에서 가능한 값은 $a=3$, $c=7$; $a=6$, $c=5$; $a=9$, $c=3$; $a=12$, $c=1$이다.