Tres gnomos — Musgo, Hoja y Raíz — bailan en círculo alrededor de un roble: Hoja sigue a Musgo, Raíz sigue a Hoja y Musgo sigue a Raíz.
Antes de la danza, cada gnomo recoge algunas bellotas para sí mismo: Musgo toma bellotas, donde 1 \le a \le n; Hoja toma bellotas, donde 1 \le b \le m; Raíz toma bellotas, donde 1 \le c \le k.
Cada gnomo coloca sus bellotas en la mayor cantidad posible de montones, de modo que cada montón contenga tantas bellotas como tiene el gnomo siguiente. Las bellotas que no caben en los montones forman el resto del gnomo. Así, los restos de Musgo, Hoja y Raíz son iguales a a \bmod b, b \bmod c y c \bmod a, donde x \bmod y es el resto de la división de entre (por ejemplo, 7 \bmod 3 = 1, 4 \bmod 11 = 4).
La danza se llama armoniosa si los restos de los tres gnomos son iguales:
Para cada uno de los casos de prueba, halla la cantidad de ternas (a, b, c) para las cuales la danza es armoniosa.
La primera línea contiene un único entero (1 \le t \le 10^5) — la cantidad de casos de prueba.
Cada una de las siguientes líneas contiene tres enteros , y (1 \le n, m, k \le 10^9).
Para cada caso de prueba, imprime en una línea separada un único entero — la cantidad de ternas (a, b, c) para las cuales la danza es armoniosa.
Ejemplo 1
En el primer caso de prueba, Raíz solo puede tomar una bellota. La única terna adecuada es (1, 1, 1): los tres restos son iguales a . Por ejemplo, la terna (2, 1, 1) no sirve: los restos de Musgo y Hoja son , mientras que el resto de Raíz es 1 \bmod 2 = 1.