{"raw_statement":[{"iden":"statement","content":"Peter is captive in W's maze which can be represented as a tridimensional matrix with lengths $N$, $M$ and $K$. Initially, Peter is in cell (1,1,1) and he needs to get to cell ($N$,$M$,$K$) to escape. From a cell, he can move to any other cell that has a wall in common with your cell (maximum $6$ other cells).   Now, everyone expects Peter to escape in the minimum number of steps, but he can do better than that. He thinks of getting out with the maximum number of steps, such that he doesn't visit a cell more than once in his path. Help Peter find the length of this path!\n\nThe first line of the input contains a number $1 <= T <= 200. 000$, the number of tests.   The next $T$ lines each contain the description of a test, 3 positive integers $1 <= N, M, K <= 10^6$.\n\nThe output should contain $T$ lines, each containing an answer to a test.\n\n"},{"iden":"input","content":"The first line of the input contains a number $1 <= T <= 200. 000$, the number of tests.   The next $T$ lines each contain the description of a test, 3 positive integers $1 <= N, M, K <= 10^6$."},{"iden":"output","content":"The output should contain $T$ lines, each containing an answer to a test."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T = (V, E) $ be a tree with $ |V| = n $, $ |E| = n - 1 $.  \nLet $ \\mathcal{P} $ denote the set of all simple paths in $ T $.\n\n**Constraints**  \n$ 2 \\leq n \\leq 200000 $\n\n**Objective**  \nFind the minimum number of paths $ P_1, P_2, \\dots, P_k \\in \\mathcal{P} $ such that:  \n$$\n\\bigcup_{i=1}^k P_i = V \\cup E\n$$  \nThat is, the union of the vertex and edge sets of the chosen paths covers all vertices and edges of $ T $.","simple_statement":"You are given a tree. You can paint a path between any two vertices in one operation. What’s the minimum number of operations to paint all vertices and edges?","has_page_source":false}