#include /* for printf, scanf */ /* The recurrence relation here is that f(n) = f(n-1) + 2(n-1), and f(1) = 2, as given in the problem. This recurrence can actually be hypothesized from the sample data given, or it can be observed by realizing that if you start to draw your nth circle in the intersection region of the existing n-1 circles, you can draw it in such a way as to hit each of those n-1 circles exactly twice, dividing each of those regions into two subregions. So in 2(n-1) places, you "net" an additional region. */ int f(int n){ return (n == 1)? 2 : f(n - 1) + 2 * (n - 1); } int main(){ int numCases, numCircles; int i; scanf("%d\n", &numCases); for (i = 0; i < numCases; i++){ scanf("%d\n", &numCircles); printf("%d\n", f(numCircles)); } return 0; }