시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 494 58 28 15.385%

문제

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

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

입력

여러 개의 문제가 하나의 입력파일 내에 주어진다. 첫째 줄에 문제의 개수 n이 주어진다. 각각의 문제는 세 개의 정수 a, b, d로 이루어져 있다. 둘째 줄부터 한 줄에 한 문제씩, 문제를 나타내는 세 정수 a, b, d가 주어진다. n과 각각의 a, b, d는 모두 50,000 이하의 자연수이며, d는 a, 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+eFx1YzY0MCB5XHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWNmNVx1YzU3ZFx1YzIxOFx1YjI5NCBkXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuIiwiaW5wdXQiOiI8cD5cdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1YmIzOFx1YzgxY1x1YWMwMCBcdWQ1NThcdWIwOThcdWM3NTggXHVjNzg1XHViODI1XHVkMzBjXHVjNzdjIFx1YjBiNFx1YzVkMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYjM4XHVjODFjXHVjNzU4IFx1YWMxY1x1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YmIzOFx1YzgxY1x1YjI5NCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBhLCBiLCBkXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NWMgXHViYjM4XHVjODFjXHVjNTI5LCBcdWJiMzhcdWM4MWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzEzOCBcdWM4MTVcdWMyMTggYSwgYiwgZFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIG5cdWFjZmMgXHVhYzAxXHVhYzAxXHVjNzU4IGEsIGIsIGRcdWIyOTQgXHViYWE4XHViNDUwIDUwLDAwMCBcdWM3NzRcdWQ1NThcdWM3NTggXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViYTcwLCBkXHViMjk0IGEsIGIgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWJiMzhcdWM4MWNcdWM3NTggXHViMmY1XHVjNzQ0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHViYjM4XHVjODFjXHVjNzU4IFx1YWNiZFx1YzZiMCwgKDIsMiksICgyLDQpLCAoNCwyKSBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YzIxY1x1YzExY1x1YzMwZFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHViYjM4XHVjODFjXHVjNzU4IFx1YWNiZFx1YzZiMCAoMywzKSwgKDYsMykgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWMyMWNcdWMxMWNcdWMzMGRcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTc5MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlF1ZXJpZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkJ5dGVhc2FyIHRoZSBDcnlwdG9ncmFwaGVyIHdvcmtzIG9uIGJyZWFraW5nIHRoZSBjb2RlIG9mIEJTQSAoQnl0ZW90aWFuIFNlY3VyaXR5IEFnZW5jeSkuIEhlIGhhcyBhbHJlYWR5IGZvdW5kIG91dCB0aGF0IHdoaWxzdCBkZWNpcGhlcmluZyBhIG1lc3NhZ2UgaGUgd2lsbCBoYXZlIHRvIGFuc3dlciBtdWx0aXBsZSBxdWVyaWVzIG9mIHRoZSBmb3JtICZxdW90O2ZvciBnaXZlbiBpbnRlZ2VycyBhLCBiIGFuZCBkLCBmaW5kIHRoZSBudW1iZXIgb2YgaW50ZWdlciBwYWlycyAoeCwgeSkgc2F0aXNmeWluZyB0aGUgZm9sbG93aW5nIGNvbmRpdGlvbnM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSAmbGU7IHggJmxlOyBhLDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgeSAmbGU7IGIsPFwvbGk+XHJcblx0PGxpPmdjZCh4LHkpID0gZCwgd2hlcmUgZ2NkKHgseSkgaXMgdGhlIGdyZWF0ZXN0IGNvbW1vbiBkaXZpc29yIG9mIHggYW5kIHkmcXVvdDsuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Qnl0ZWFzYXIgd291bGQgbGlrZSB0byBhdXRvbWF0ZSBoaXMgd29yaywgc28gaGUgaGFzIGFza2VkIGZvciB5b3VyIGhlbHAuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbW1lIHdoaWNoOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnJlYWRzIGZyb20gdGhlIHN0YW5kYXJkIGlucHV0IGEgbGlzdCBvZiBxdWVyaWVzLCB3aGljaCB0aGUgQnl0ZWFzYXIgaGFzIHRvIGdpdmUgYW5zd2VyIHRvLDxcL2xpPlxyXG5cdDxsaT5jYWxjdWxhdGVzIGFuc3dlcnMgdG8gdGhlIHF1ZXJpZXMsPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0aGUgb3V0Y29tZSB0byB0aGUgc3RhbmRhcmQgb3V0cHV0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgY29udGFpbnMgb25lIGludGVnZXIgbiAoMSAmbGU7IG4gJmxlOyA1MCAwMDApLCBkZW5vdGluZyB0aGUgbnVtYmVyIG9mIHF1ZXJpZXMuIFRoZSBmb2xsb3dpbmcgbiBsaW5lcyBjb250YWluIHRocmVlIGludGVnZXJzIGVhY2g6IGEsIGIgYW5kIGQgKDEgJmxlOyBkICZsZTsgYSxiICZsZTsgNTAgMDAwKSwgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMuIEVhY2ggdHJpcGxldCBkZW5vdGVzIGEgc2luZ2xlIHF1ZXJ5LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbW1lIHNob3VsZCB3cml0ZSBuIGxpbmVzIHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQuIFRoZSBpJiMzOTt0aCBsaW5lIHNob3VsZCBjb250YWluIGEgc2luZ2xlIGludGVnZXI6IHRoZSBhbnN3ZXIgdG8gdGhlIGkmIzM5O3RoIHF1ZXJ5IGZyb20gdGhlIHN0YW5kYXJkIGlucHV0LjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+VGhlIHBhaXJzIHNhdGlzZnlpbmcgdGhlIGZpcnN0IHF1ZXJ5IGFyZTogKDIsMiksICgyLDQpIGFuZCAoNCwyKS4gVGhlIHBhaXJzIHNhdGlzZnlpbmcgdGhlIHNlY29uZCBxdWVyeSBhcmU6ICg2LDMpIGFuZCAoMywzKS48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==