시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB178130518518.574%

문제

세 개의 정수 a, b, d가 주어지면, 다음의 세 조건을 만족하는 자연수 순서쌍 (x, y)의 개수를 구하는 프로그램을 작성하시오.

  1. 1 ≤ x ≤ a
  2. 1 ≤ y ≤ b
  3. x와 y의 최대공약수는 d이다.

입력

여러 개의 문제가 하나의 입력파일 내에 주어진다. 첫째 줄에 문제의 개수 n이 주어진다. 각각의 문제는 세 개의 정수 a, b, d로 이루어져 있다. 둘째 줄부터 한 줄에 한 문제씩, 문제를 나타내는 세 정수 a, b, d가 주어진다.

출력

각 문제의 답을 한 줄에 하나씩 출력하도록 한다.

제한

  • 1 ≤ N ≤ 50,000
  • 1 ≤ a, b, d ≤ 50,000
  • d ≤ a
  • d ≤ b

예제 입력 1

2
4 5 2
6 4 3

예제 출력 1

3
2

힌트

첫 번째 문제의 경우, (2,2), (2,4), (4,2) 세 개의 순서쌍이 존재한다. 두 번째 문제의 경우 (3,3), (6,3) 두 개의 순서쌍이 존재한다.

W3sicHJvYmxlbV9pZCI6IjE3OTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZjVcdWM1N2RcdWMyMTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzEzOCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IGEsIGIsIGRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTc0LCBcdWIyZTRcdWM3NGNcdWM3NTggXHVjMTM4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjNzkwXHVjNWYwXHVjMjE4IFx1YzIxY1x1YzExY1x1YzMwZCAoeCwgeSlcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPjEgJmxlOyB4ICZsZTsgYTxcL2xpPlxyXG5cdDxsaT4xICZsZTsgeSAmbGU7IGI8XC9saT5cclxuXHQ8bGk+eFx1YzY0MCB5XHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWNmNVx1YzU3ZFx1YzIxOFx1YjI5NCBkXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuIiwiaW5wdXQiOiI8cD5cdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1YmIzOFx1YzgxY1x1YWMwMCBcdWQ1NThcdWIwOThcdWM3NTggXHVjNzg1XHViODI1XHVkMzBjXHVjNzdjIFx1YjBiNFx1YzVkMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYjM4XHVjODFjXHVjNzU4IFx1YWMxY1x1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YmIzOFx1YzgxY1x1YjI5NCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBhLCBiLCBkXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NWMgXHViYjM4XHVjODFjXHVjNTI5LCBcdWJiMzhcdWM4MWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzEzOCBcdWM4MTVcdWMyMTggYSwgYiwgZFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWIyZjVcdWM3NDQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTU4XHViM2M0XHViODVkIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM4MWNcdWM3NTggXHVhY2JkXHVjNmIwLCAoMiwyKSwgKDIsNCksICg0LDIpIFx1YzEzOCBcdWFjMWNcdWM3NTggXHVjMjFjXHVjMTFjXHVjMzBkXHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC4gXHViNDUwIFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM4MWNcdWM3NTggXHVhY2JkXHVjNmIwICgzLDMpLCAoNiwzKSBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzIxY1x1YzExY1x1YzMwZFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IE4gJmxlOyA1MCwwMDA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IGEsIGIsIGQgJmxlOyA1MCwwMDA8XC9saT5cclxuXHQ8bGk+ZCAmbGU7IGE8XC9saT5cclxuXHQ8bGk+ZCAmbGU7IGI8XC9saT5cclxuPFwvdWw+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjE3OTIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJRdWVyaWVzIiwiZGVzY3JpcHRpb24iOiI8cD5CeXRlYXNhciB0aGUgQ3J5cHRvZ3JhcGhlciB3b3JrcyBvbiBicmVha2luZyB0aGUgY29kZSBvZiBCU0EgKEJ5dGVvdGlhbiBTZWN1cml0eSBBZ2VuY3kpLiBIZSBoYXMgYWxyZWFkeSBmb3VuZCBvdXQgdGhhdCB3aGlsc3QgZGVjaXBoZXJpbmcgYSBtZXNzYWdlIGhlIHdpbGwgaGF2ZSB0byBhbnN3ZXIgbXVsdGlwbGUgcXVlcmllcyBvZiB0aGUgZm9ybSAmcXVvdDtmb3IgZ2l2ZW4gaW50ZWdlcnMgYSwgYiBhbmQgZCwgZmluZCB0aGUgbnVtYmVyIG9mIGludGVnZXIgcGFpcnMgKHgsIHkpIHNhdGlzZnlpbmcgdGhlIGZvbGxvd2luZyBjb25kaXRpb25zOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgJmxlOyB4ICZsZTsgYSw8XC9saT5cclxuXHQ8bGk+MSAmbGU7IHkgJmxlOyBiLDxcL2xpPlxyXG5cdDxsaT5nY2QoeCx5KSA9IGQsIHdoZXJlIGdjZCh4LHkpIGlzIHRoZSBncmVhdGVzdCBjb21tb24gZGl2aXNvciBvZiB4IGFuZCB5JnF1b3Q7LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkJ5dGVhc2FyIHdvdWxkIGxpa2UgdG8gYXV0b21hdGUgaGlzIHdvcmssIHNvIGhlIGhhcyBhc2tlZCBmb3IgeW91ciBoZWxwLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW1tZSB3aGljaDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5yZWFkcyBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCBhIGxpc3Qgb2YgcXVlcmllcywgd2hpY2ggdGhlIEJ5dGVhc2FyIGhhcyB0byBnaXZlIGFuc3dlciB0byw8XC9saT5cclxuXHQ8bGk+Y2FsY3VsYXRlcyBhbnN3ZXJzIHRvIHRoZSBxdWVyaWVzLDxcL2xpPlxyXG5cdDxsaT53cml0ZXMgdGhlIG91dGNvbWUgdG8gdGhlIHN0YW5kYXJkIG91dHB1dC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIHN0YW5kYXJkIGlucHV0IGNvbnRhaW5zIG9uZSBpbnRlZ2VyIG4gKDEgJmxlOyBuICZsZTsgNTAgMDAwKSwgZGVub3RpbmcgdGhlIG51bWJlciBvZiBxdWVyaWVzLiBUaGUgZm9sbG93aW5nIG4gbGluZXMgY29udGFpbiB0aHJlZSBpbnRlZ2VycyBlYWNoOiBhLCBiIGFuZCBkICgxICZsZTsgZCAmbGU7IGEsYiAmbGU7IDUwIDAwMCksIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLiBFYWNoIHRyaXBsZXQgZGVub3RlcyBhIHNpbmdsZSBxdWVyeS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW1tZSBzaG91bGQgd3JpdGUgbiBsaW5lcyB0byB0aGUgc3RhbmRhcmQgb3V0cHV0LiBUaGUgaSYjMzk7dGggbGluZSBzaG91bGQgY29udGFpbiBhIHNpbmdsZSBpbnRlZ2VyOiB0aGUgYW5zd2VyIHRvIHRoZSBpJiMzOTt0aCBxdWVyeSBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBwYWlycyBzYXRpc2Z5aW5nIHRoZSBmaXJzdCBxdWVyeSBhcmU6ICgyLDIpLCAoMiw0KSBhbmQgKDQsMikuIFRoZSBwYWlycyBzYXRpc2Z5aW5nIHRoZSBzZWNvbmQgcXVlcnkgYXJlOiAoNiwzKSBhbmQgKDMsMykuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > Polish Olympiad in Informatics > POI 2006/2007 > Stage 1 5번