K. Пирог: сколько ходов

Тот же пирог, что в классной задаче K. Посчитайте, сколькими разными ходами первый игрок может выиграть.

Ход - это пара «какое измерение режем» и «какой размер остаётся». Два хода считаются разными, если различается хотя бы одна из этих величин.

В первой строке - число запросов $q$ ($1 \le q \le 10^4$).

В следующих $q$ строках - по три числа $a$, $b$, $c$ ($1 \le a, b, c \le 5000$).

Для каждого запроса выведите количество выигрышных первых ходов, каждое в отдельной строке.