# DCP-550: Interesting Lab Task Back to All Problems

Medium Math > Number Theory

**Mr. X** has given a lab task to his students. He has provided them with a pseudo code of a function. Their task is to implement a similar function that will give same output as the following function. Func(n) { ret = 0 for( i = 1; i < n; i++) { if( gcd(i,n) > 1) { ret = ret + i } } return ret } Input: ------ Input starts with an integer **T (1 ≤ T ≤ 1500)**, denoting the number of test cases. Each of the next **T** lines contain an integer **n (1 ≤ n ≤ 1,000,000,000)**. Output: ------- For each integer **n**, print the value of **Func(n)** in a line. Follow the output format of the sample. Sample Input ------------ 3 4 6 9 Sample Output ------------- 2 9 9

### Problem Limits

 Language Time Limit (seconds) C 1.00 C++ 1.00 C++14 1.00 C# 2.00 Go 2.00 Java 2.00 JavaScript 2.00 Objective-C 2.00 Perl 2.00 PHP 2.00 Python 2.00 Python3 2.00 Ruby 2.00 VB.Net 2.00

# 49/218

Solve/Submission

### Ranking

# User Language Timing
01 feodorv C 0.02s
02 H_alexa Cpp 0.04s
03 RHT_20 Cpp 0.04s
04 Rajib_119 Cpp 0.04s
06 rifat_ikbal007 Cpp 0.05s
07 mahbubcseju Cpp 0.05s
08 shahjalalshohag Cpp14 0.05s
10 ToErr Cpp 0.05s
11 Mubin_BUBT38 Cpp 0.05s
13 mash02 Cpp 0.06s
16 kzvd4729 Cpp14 0.06s
17 sayedgkm Cpp 0.08s
18 mobasshir Cpp 0.08s
19 Old_kernel Cpp14 0.08s
20 nahid08 Cpp 0.09s
21 st3inum Cpp14 0.09s
22 Raihanur_R Cpp 0.09s
23 Bappy Cpp14 0.10s
24 mir003 Cpp 0.10s
25 liar Cpp 0.11s
26 Dalgerok Cpp14 0.12s
27 PKP_007 Cpp 0.12s
28 xeon Cpp14 0.12s
29 _c_k_r_ Cpp 0.13s
30 ssavi Cpp 0.14s
32 Double_O Cpp14 0.15s
33 ksohan Cpp 0.22s
34 codebreaker007 Cpp 0.22s
35 ifahim1000 Cpp14 0.35s
36 tariqiitju Cpp14 0.37s
37 Taran Cpp14 0.38s
38 Bruteforcekid Cpp14 0.39s
39 snow_man Cpp14 0.39s
40 pulak_ict_mbstu Cpp14 0.40s
41 simantaturja Cpp 0.40s
42 shamimjucse Cpp 0.40s