{"raw_statement":[{"iden":"statement","content":"Consider the following equation \n\nGiven a, b and m, your task is to find a value x that satisfy the equation for the given values. Can you?\n\nThe first line contains an integer T (1 ≤ T ≤ 500), in which T is the number of test cases.\n\nEach test case consists of a line containing three integers a, b and m (0 ≤ a, b < m ≤ 109).\n\nFor each test case, print a single line containing an integer x (0 ≤ x ≤ 1017) that satisfy the equation , for the given a, b and m. \n\nIf there are multiple solutions, print any of them. It is guaranteed that an answer always exist for the given input.\n\n"},{"iden":"input","content":"The first line contains an integer T (1 ≤ T ≤ 500), in which T is the number of test cases.Each test case consists of a line containing three integers a, b and m (0 ≤ a, b < m ≤ 109)."},{"iden":"output","content":"For each test case, print a single line containing an integer x (0 ≤ x ≤ 1017) that satisfy the equation , for the given a, b and m. If there are multiple solutions, print any of them. It is guaranteed that an answer always exist for the given input."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, t \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, t \\leq 2 \\times 10^5 $.  \nLet $ \\text{id} = (id_1, id_2, \\dots, id_n) $ be a sequence of positive integers with $ 1 \\leq id_i \\leq 5 \\times 10^5 $.  \nFor each sword $ i $, define its *characteristic set* as:  \n$$\nC_i = \\{ c \\in \\mathbb{Z} \\mid c > 1 \\text{ and } c \\mid id_i \\}\n$$  \nTwo swords $ i $ and $ j $ are *compatible* if $ C_i \\cap C_j = \\emptyset $.  \n\nLet $ S \\subseteq \\{1, 2, \\dots, n\\} $ be the set of swords currently in stock. Initially, $ S = \\emptyset $.  \n\n**Constraints**  \n- Each event updates $ S $: for event $ x $, if $ x \\in S $, remove $ x $; else, add $ x $.  \n- After each update, compute the number of unordered pairs $ \\{i, j\\} \\subseteq S $ with $ i \\ne j $ and $ C_i \\cap C_j = \\emptyset $.  \n\n**Objective**  \nFor each of the $ t $ events, output:  \n$$\n\\left| \\left\\{ \\{i, j\\} \\subseteq S \\mid i \\ne j \\text{ and } C_i \\cap C_j = \\emptyset \\right\\} \\right|\n$$","simple_statement":"Asuna wants to buy two compatible swords for Kirito.  \nTwo swords are compatible if they share no common factor greater than 1.  \nThere are n swords, each with an ID. Initially, none are in stock.  \nt events happen: each event flips the stock status of one sword (in → out, or out → in).  \nAfter each event, count how many valid pairs of currently in-stock swords are compatible.","has_page_source":false}