{"problem":{"name":"G. Hard Equation","description":{"content":"Consider the following equation  Given a, b and m, your task is to find a value x that satisfy the equation for the given values. Can you? The first line contains an integer T (1 ≤ T ≤ 500), in whic","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":10000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10185G"},"statements":[{"statement_type":"Markdown","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## Input\n\nThe 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).\n\n## Output\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. If there are multiple solutions, print any of them. It is guaranteed that an answer always exist for the given input.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10185G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}