Relation between Entropy and Temperature I have read the Entropy is defined by:
S = Q/T
which means that Entropy is indirectly proportional to temperature. Still we say that Entropy increases as temperature increases.
For example, if the temperature of a crystal is increased from 0K to 115K, we would instinctively say that entropy is increasing because kinetic energy of the particles is increasing which is leading to more randomness.
Both things contradict.
What am I missing here?
 A: 
I have read the Entropy is defined by:  S = Q/T

Entropy is not defined by that equation. A differential change in entropy is defined by
$$dS=\frac{\delta Q_{rev}}{T}\tag{1}$$
Where $\delta Q_{rev}$ is a reversible transfer of heat.  Then
$$\Delta S_{1-2}=\int_1^2\frac{\delta Q_{rev}}{T}\tag{2}$$

which means that Entropy is indirectly proportional to temperature.

Your conclusion that absolute entropy is inversely proportional to temperature rise is incorrect because $Q$ is a variable. To determine the entropy change you need to evaluate equation (2) for a reversible path between the initial and final equilibrium temperatures.

Still we say that Entropy increases as temperature increases.

Not necessarily.
Case in point is the reversible adiabatic (isentropic) compression of an ideal gas in which the temperature of the gas increases. Since the process is both adiabatic and reversible $\delta Q_{rev}=0$ and thus it follows from equations (1) and (2) the change in entropy is zero.
At the microscopic level, the increase in temperature results in greater molecular disorder and an increase in entropy. But the lower volume provides fewer ways to distribute the molecules (energy) reducing disorder and entropy. The result is a net change in entropy of the gas of zero.
Hope this helps.
A: The formula has $2$ variables, because heat is not a constant.
Heat is a flow of energy, and we must understand the change of entropy as a result of that flow. Normally the temperature increases when there is an heat input in a mass of material, So, energy and temperature are related. But they don't tell the whole history.
It is necessary $334 kJ$ to melt $1kg$ of water at $273 K$, but the temperature doesn't change in the process. So, the mass has more energy and the same temperature when liquid, compared to solid. And there is a change of entropy: $$\Delta S = \frac{\Delta Q}{T} = \frac{334}{273} = 1.22 kJ/K$$
In order to boil $1kg$ of water at $373 K$, it is necessary $2265 kJ$. Now the change of entropy is:$$\Delta S = \frac{2265}{373} = 6.07 kJ/K$$
So, the denominator increased, but the numerator increased much more.
When the temperature increases along the heat input, the entropy also increases, but the example of a process without change of temperature is more clear in my opinion.
