Three gnomes — Moss, Leaf, and Root — dance in a circle around an oak tree: Leaf follows Moss, Root follows Leaf, and Moss follows Root.
Before the dance, each gnome gathers some acorns for himself: Moss takes acorns, where 1 \le a \le n; Leaf takes acorns, where 1 \le b \le m; Root takes acorns, where 1 \le c \le k.
Each gnome arranges his acorns into as many piles as possible, each pile containing as many acorns as the next gnome has. The acorns that do not fit into piles are the gnome's remainder. Thus, the remainders of Moss, Leaf, and Root are equal to a \bmod b, b \bmod c, and c \bmod a, where x \bmod y is the remainder of dividing by (for example, 7 \bmod 3 = 1, 4 \bmod 11 = 4).
The dance is called harmonious if the remainders of all three gnomes are equal:
For each of test cases, find the number of triples (a, b, c) for which the dance is harmonious.
The first line contains a single integer (1 \le t \le 10^5) — the number of test cases.
Each of the next lines contains three integers , , and (1 \le n, m, k \le 10^9).
For each test case, output on a separate line a single integer — the number of triples (a, b, c) for which the dance is harmonious.
Example 1
In the first test case, Root can take only one acorn. The only suitable triple is (1, 1, 1): all three remainders are equal to . For example, the triple (2, 1, 1) is not suitable: the remainders of Moss and Leaf are , while the remainder of Root is 1 \bmod 2 = 1.