CodeChef : October Challenge 2016 – Chef and Keyboard

By | October 8, 2016

Chef is a well known programmer. He owns a brand new Android phone of screen size of dimension n × m. Chef wants to design a program for painting the screen. He figured out c colors, which he will use to paint the screen. He wants to paint some rectangular section of pixels of the screen each with different color. Also Chef would like to use all of his c colors in painting.

Can you help Chef in finding number of different dimensions of rectangular section he can paint? In other words, find number of pairs x, y such that Chef can paint a rectangular section of dimension x × y on the screen. Please note that Chef uses a fix orientation of his phone and is not allowed to rotate it.

Input

First line of the input contains an integer T denoting the number of test cases. T test cases follow.

Only line of each test case contains three space separated integers n, m, c.

Output

For each test case, output a single line containing the answer for the test case.

Constraints

  • 1T100
  • 1n, m106
  • 1c106

Subtasks

  • Subtask #1: (40 points) 1n, m100, 1c104
  • Subtask #2: (60 points) original constraints

Example

Input:
2
4 6 12
3 3 10

Output:
3
0

Explanation

Test case 1. Possible pairs of dimensions are (2, 6), (3, 4) and (4, 3). Note that the rectangular section of dimension (1, 12) can’t be painted as it can’t fit into the screen, because 12 > 6.

Test case 2. There does not exist any rectangle of desired dimensions which can have 10 different pixels painted.

Solution

Run nested loops, outside one till n and inside one till m. Calculate their 
multiplication and check if it is equal to the color count provided , if 
yes then increase the count value. 
Count value will be the answer.